[자료구조/알고리즘]재귀(recursion)

김밍·2023년 4월 11일

CODESTATES Section3

코드스테이츠

목록 보기

1/3

오늘은 재귀에 대한 내용을 배웠다. 먼소린가 싶어서 깜짝 놀랐다..ㅜㅜ

재귀의 개념

재귀(recursion)란? 원래의 자리로 되돌아가거나 되돌아오는 것을 의미한다.

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

재귀의 정의를 참고하여 코드로 표현하면 위의 코드와 같이 작성할 수 있다.
이 함수를 호출해보면

해당과 같은 결과를 볼 수 있다.

recursion함수를 호출했더니 자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 것을 볼 수 있다.
이 recursion함수처럼 자기 자신을 호출하는 함수를 재귀함수(recursion function)라고 한다.

재귀 함수를 잘 활용하면 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.

재귀로 문제 해결하기

그렇다면 어떻게 재귀를 잘 활용해서 문제를 해결할 수 있는지 예제를 보면서 따라가보자

Q. 자연수로 이루어진 리스트(배열)을 입력받고, 리스트의 합을 리턴하는 함수'arrSum'을 작성하세요

위 문제는 반복문을 통해서 풀 수 있지만 재귀를 통해서 한번 해결해보자

재귀를 이용하여 문제를 해결하는 단계

1. 문제를 좀 더 작게 뽀갠다.
2. 1번과 같은 방식으로 문제가 더 이상 작아지지 않을때까지 가장 작은 단위로 문제를 뽀갠다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

1. 문제를 작게 뽀개기

어떻게 하면 arrSum함수로 [1, 2, 3, 4, 5]의 합을 구하는 과정을 더 작게 뽀갤 수 있을까?
단순하게 생각해보면 1, 2, 3, 4, 5의 합을 구하는 것 보다는 2, 3, 4, 5의 합을 구하는것이 더 작은 문제고, 여기서 또 2, 3, 4, 5의 합을 구하는것보다 3, 4, 5의 합을 구하는 것이 더 작은 문제일 것이다.

위와 같이 뽀갠 것을 코드로 표현하면 다음과 같다.

arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
...

2. 문제를 가장 작은 단위로 뽀개기

위에서 문제를 뽀갠 방식을 반복해서 문제를 계속해서 뽀개다보면 더 이상 뽀개질 수 없는 상태에 도달하게 된다.

...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])

마지막에 arrSum이 빈 배열을 받게 되면서 더 이상 뽀갤수없게 됨으로써 문제를 가장 작은 단위까지 뽀갈랐다고 할 수 있다.

3. 문제 해결하기

문제가 더 이상 뽀개지지 않게 되면 가장 작은 단위의 문제를 해결한다.
문제를 뽀갤때 같은 방식으로 뽀갰기 때문에 가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결할 수 있게 된다.
2번에서 도달한 가장 작은 문제는 arrSum([])이었다.
빈 배열의 합은 0이므로 0을 리턴해주면 될 것이다.
이렇게 가장 작은 문제를 해결하는 순간 아래 코드처럼 뽀개졌던 문제가 거꾸로 올라가면서 합쳐지게 된다.

function arrSum(arr) {
  //빈 배열을 받았을때 0을 리턴하는 조건문
  // => 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if(arr.length === 0) {
    return 0
  }
  //배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  // => 재귀(자기 자신을 호출)를 통해 문제를 작게 뽀개나가는 코드
  return arr.shift() + arrSum(arr)
}

재귀는 언제 사용하는것이 좋을까?

재귀는 다음과 같은 상황에서 매우 적합하다.

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

모든 재귀함수는 반복문(while 또는 for문)으로 표현할 수 있다.
그러나 재귀를 적용할 수 있는 대부분의 경우에는 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.
이 밖에도 재귀는 알고리즘 문제의 많은 부분을 차지한다.

재귀의 활용

재귀적 사고를 더욱 쉽게 할 수 있는 가이드를 함께 알아보자

재귀적으로 사고하기

1. 재귀함수의 입력값과 출력값 정의하기
2. 문제를 뽀개고 경우의 수 나누기
3. 단순한 문제 해결하기
4. 복잡한 문제 해결하기
5. 코드 구현하기

1. 재귀함수의 입력값과 출력값 정의하기

재귀적으로 사고하는데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는 가장 단순하게 정의하는 것이다.
함수의 입출력값을 정의하는 것은 그 출발점이며 재귀함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는데 도움이 된다.

함수 arrSum의 경우 number타입을 요소로 갖는 배열을 입력으로 받고, number타입을 리턴한다.
이를 좀 더 간결하게 표기하면 다음과 같다.

arrSum : [number] => number

2. 문제를 뽀개고 경우의 수 나누기

주어진 문제를 어떻게 뽀갤것인지 고민한다.
문제를 뽀갤 기준을 정하고 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지를 확인한다.
입력값을 이 기준으로 정한다.
이때 중요한 관점은 입력값이나 문제의 순서와 크기이다.
주어진 입력값 또는 문제상황을 크기로 구분할 수 있거나 순서를 명확하게 정할 수 있다면 문제를 구분하는데 도움이 된다.
그리고 구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같다면 문제를 제대로 구분한 것이다.

함수 arrSum의 경우 입력값인 배열의 크기에 따라 더 작은 문제로 나눌 수 있다.
그리고 arrSum([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])를 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.
이제 문제에서 주어진 입력값에 따라 경우의 수를 나눈다. 일반적으로 문제를 더 이상 뽀갤 수 없는 경우와 그렇지 않은 경우로 나눈다
함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다.
각각의 경우는 다른 방식으로 처리해야 한다.
- arrSum : [number] => number
- arrSum([]) <- 입력값이 빈 배열인 경우
- arrSum([요소1, 요소2, ..., 요소n]) <- 그렇지 않은 경우

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는 가장 해결하기 쉬운 문제부터 해결한다.
이를 재귀의 기초(base case)라고 부른다.
재귀의 기초는 나중에 재귀함수를 구현할 때 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.
탈출 조건이 없는 경우 재귀함수는 끝없이 자기 자신을 호출하게 된다.
그렇다고 문제를 덜 뽀갠 상태에서 탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없게 된다.
그만큼 문제를 최대한 작게 뽀갠 후에 해결하는 것이 중요하다.

함수 arrSum을 더 이상 뽀갤 수 없는 경우는 입력값이 빈 배열인 경우이고, 이때 arrSum([])의 리턴값은 0이다.
- arrSum: [number] => number
- arrSum([]) === 0 <- 입력값이 빈 배열인 경우 : 해결!
- arrSum([요소1, 요소2, ..., 요소n])

4. 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결한다.

길이가 1이상인 배열이 함수 arrSum에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 뽀개고, 둘을 더한다.
arrSum: [number] => number
arrSum([]) === 0
arrSum([요소1, 요소2, ..., 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) <- 그렇지 않은 경우: 해결!
배열을 첫 요소와 더 작은 문제로 뽀개는 방법만 안다면 함수 arrSum을 재귀적으로 구현할 수 있다.

5. 코드 구현하기

function arrSum(arr) {
  //base case : 문제를 더 이상 뽀갤 수 없는 경우(재귀의 기초)
  if(arr의 길이가 0인 경우) {
    return 0
  }
  //recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ..., 요소n]);
}

정리

재귀란, 더이상 나눠지지 않을때까지 뽀개는것이 중요하다.
이후 가장 작은 단위의 문제를 해결함으로써 문제 전체를 해결할 수 있다.

재귀의 기초(base case) : 나중에 재귀함수를 구현할 때 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.
recursive case : 그렇지 않은 경우를 의미한다.

// 일반적인 재귀함수의 템플릿
function recursive(input1, input2, ...) {
  //base case : 문제를 더 이상 뽀갤 수 없는 경우
  if(문제를 더 이상 뽀갤 수 없는 경우) {
    return 단순한 문제의 해답;
  }
  //recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}