재귀

재귀함수

---

재귀란 원래의 자리로 되돌아가거나 되돌아오는 것을 말하는 것으로 코드에서 자기 자신을 호출하는 함수인 재귀(recursion) 함수를 자주 접할 수 있다. 이를 잘 활용하면 반복적인 작업을 해야하는 문제를 좀더 간결한 코드로 풀어낼 수 있다.

//재귀 함수의 예

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

재귀로 문제 해결해보기

---

재귀 없이 반복문으로 해결하는 방법도 있지만 재귀를 활용해 해결하는 방법을 알아놓는 것도 매우 중요하다. 우선 이론적으로 재귀로 문제를 해결하는 단계 3단계로 나뉜다.

재귀를 활용해 문제를 풀기 위한 과정

---

1. 문제를 좀 더 작게 쪼갠다.

2. 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.

3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

위의 과정을 예시 문제를 풀어보며 더욱 자세히 알아보자.

예시 문제

---

자연주로 이루어진 리스트(배열)를 입력받고 리스트의 합을 리턴하는 함수 'arrSum'을 작성하시오

일단 배열 [1, 2, 3, 4, 5] 의 합을 구하는 과정을 전제로 놓겠다.

문제 잘게 쪼개기

단순하게 생각해보면 배열의 합을 구할 때 [1, 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])
...

문제를 가장 작은 단위로 쪼개기

위에서 문제를 쪼갠 방식을 반복하다보면 더 이상 쪼갤 수 없는 상태에 도달한다.

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

문제 해결하기

문제가 더 쪼개지지 않게 되면 가장 작은 단위의 문제를 해결해보자. 문제를 쪼갤 때 같은 방식으로 쪼갰으니 가장 작은 단위 문제를 해결한 방식으로 문제 전체를 해결 할 수 있다.

arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;

위에서 도달한 가장 작은 문제는 arrSum([])이었다. 빈배열의 합은 0으로, 0을 리턴해주면 된다. 이렇게 가장 작은 문제를 해결하는 순간 위 코드처럼 거꾸로 거슬러 올라가며 합쳐보자. arrSum의 함수의 리턴 값이 나오며 연쇄적으로 문제가 해결되고, 최종저으로는 문제 전체가 해결되는 것을 볼 수 있다.

이를 반영해 arrSum 함수를 완성해보면 다음과 같다.

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length === 0) {
    return 0
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr)
}

재귀는 언제 사용할까

---

재귀를 사용하는 적합한 경우

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

// 재귀 사용에 적합한 예

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

모든 재귀 함수는 반복문으로도 표현이 가능하지만 재귀를 적용할 수 있는 대부분의 경우에는 재귀를 적용한 코드가 더욱 간결하고 이해가 쉽다. 이 밖에도 여러 알고리즘 문제의 많은 부분을 차지하기 때문에 확실히 익혀두는 게 좋다.

재귀적 사고

---

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 recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

이를 참고로 arrSum 의 코드를 구현해보면

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }

  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}