재귀의 개념
재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.
재귀를 코드로 표현하면 다음과 같이 작성할 수 있다.
function recursion () {
console.log("This is")
console.log("recursion!")
recursion()
}이 함수를 호출하면 어떻게 될까?
recursion 함수를 호출했더니, 자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 것을 볼 수 있다. 이 recursion 함수처럼 자기 자신을 호출하는 함수를 재귀 함수라고 한다. 재귀 함수를 잘 활용하면 반복적인 작업을 해야 하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.
재귀로 문제 해결하기
문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수
arrSum을 작성하세요.
물론 재귀 없이 반복문으로 해결하는 방법도 있다. 하지만 재귀를 배우는 것이 목적이니, 연습해 보자. 우선 이론적으로 재귀로 문제를 해결하는 단계는 다음과 같다.
- 문제를 좀 더 작게 쪼갠다.
- 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.
- 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.
이 단계를 적용해서 arrSum 함수를 작성해 보자. 일단 배열 [1, 2, 3, 4, 5] 의 합을 구하는 과정을 재귀로 풀어보자.
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을 리턴해주면 된다. 이렇게 가장 작은 문제를 해결하는 순간, 아래 코드처럼 쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐지게 된다.
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 함수의 리턴 값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결되는 것을 볼 수 있다.
위 단계를 반영해서 arrSum 함수를 완성해 보면 다음과 같다.
function arrSum (arr) {
// 빈 배열을 받았을 때 0을 리턴하는 조건문
// --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
if (arr.length === 0) {
return 0
}
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
return arr.shift() + arrSum(arr)
}재귀는 언제 사용하는 게 좋을까?
재귀는 다음과 같은 상황에서 매우 적합하다.
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수(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);
}
}
}
}
}
}
}
}모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.
