재귀(再歸)(Recursion) : 원래의 자리로 되돌아가거나 되돌아옴.
즉 자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 함수다.
재귀 함수를 잘 활용하면 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.
재귀로 문제 해결하기
문제: 자연수로 이루어진 리스트(배열)를 입력받고,
리스트의 합을 리턴하는 함수 `arrSum` 을 작성하세요.
물론 재귀 없이 반복문으로 해결하는 방법도 있다.
하지만 이번 챕터는 재귀를 배우는 것이 목적이니, 차근차근 따라오며 재귀를 이해해보자.
우선 이론적으로 재귀로 문제를 해결하는 단계는 다음과 같다.
문제를 좀 더 작게 쪼갠다.
1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.
가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.
이 단계를 적용해서 arrSum 함수를 작성해보자. 일단 배열 [1, 2, 3, 4, 5] 의 합을 구하는 과정을 재귀로 풀어본다.
단순하게 생각해보면, 배열의 합을 구할 때 [1, 2, 3, 4, 5] 의 합을 구하는 것보다 [2, 3, 4, 5] 의 합을 구하는 것이 더 작은 문제이고, 여기서 또 [2, 3, 4, 5] 의 합을 구하는 것보다 [3, 4, 5] 의 합을 구하는 것이 더 작은 문제일 것이다.
위 방식으로 문제를 쪼갠것을 코드로 표현하면 다음과 같다.
1 arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
2 arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
3 ...
1 ...
2 arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
3 arrSum([4, 5]) === 4 + arrSum([5])
4 arrSum([5]) === 5 + arrSum([])
마지막에는 arrSum 이 빈 배열을 받게되면서 문제를 더이상 쪼갤 수 없게 되었다. 이로써 문제를 가장 작은 단위까지 쪼갰다고 할 수 있게 되었다.
2번에서 도달한 가장 작은 문제는 arrSum([]) 이었다. 빈 배열의 합은 0이므로, 0을 리턴해주면 된다. 이렇게 가장 작은 문제를 해결하는 순간, 아래 코드처럼 쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐지게 된다.
1 arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
2 arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
3 arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
4 arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
5 arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
6 arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;
arrSum 함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결되는 것을 볼 수 있다.
위 단계를 반영해서 arrSum 함수를 완성해보면 다음과 같다.
1 function arrSum (arr) {
2 // 빈 배열을 받았을 때 0을 리턴하는 조건문
3 // --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
4 if (arr.length === 0) {
5 return 0
6 }
7
8 // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
9 // --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
10 return arr.shift() + arrSum(arr)
11 }
재귀는 언제 사용하는 게 좋을까?
재귀는 다음과 같은 상황에서 매우 적합하다.
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);
}
}
}
}
}
}
}
}
모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.
이 밖에도, 재귀는 알고리즘 문제의 많은 부분을 차지한다. 앞으로 만나게 될 다양한 과제와 기업의 입사 시험(코딩 테스트, 알고리즘 테스트 등)이나 직무면접에서 활용할 수 있기 때문에, 기초를 확실하게 다져두는 게 바람직하다.
함수 arrSum 의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴한다. 이를 좀 더 간단하게 표기하면 다음과 같다.
arrSum: [number] => number ← 입출력값 정의
함수 arrSum 의 경우 입력값인 배열의 크기에 따라, 더 작은 문제로 나눌 수 있다. 그리고 arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.
이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눈다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나뉜다.
함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 각각의 경우는 다른 방식으로 처리해야 한다.
arrSum: [number] => number
arrSum([ ]) ← 입력값이 빈 배열인 경우
arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우
탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 된다. 그렇다고 문제를 덜 쪼갠 상태에서 탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없게 된다. 그만큼 문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요하다.
함수 arrSum 을 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0이다.
arrSum: [number] => number
arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
arrSum([요소1, 요소2, ... , 요소n])
길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더한다.
arrSum: [number] => number
arrSum([ ]) === 0
arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있다.
아래는 일반적인 재귀 함수의 템플릿이다. 재귀 함수 연습에 활용하자.
1 function recursive(input1, input2, ...) {
2 // base case : 문제를 더 이상 쪼갤 수 없는 경우
3 if (문제를 더 이상 쪼갤 수 없을 경우) {
4 return 단순한 문제의 해답;
5 }
6
7 // recursive case : 그렇지 않은 경우
8 return 더 작은 문제로 새롭게 정의된 문제
9 }