function recursion () {
console.log("This is")
console.log("recursion!")
recursion()
}
recursion
함수를 호출했더니, 자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 것을 볼 수 있다.recursion
함수처럼 자기 자신을 호출하는 함수를 재귀 함수라고 하며,어떻게 하면 재귀를 활용해서 문제를 해결할 수 있을까?
문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수
arrSum
을 작성하세요.
function arrSum(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
- 문제를 좀 더 작게 쪼갠다.
- 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])
...
...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])
arrSum
이 빈 배열을 받게 되면서 문제를 더 이상 쪼갤 수 없게 되었다.문제가 더 쪼개지지 않게 되면, 가장 작은 단위의 문제를 해결한다.
문제를 쪼갤 때 같은 방식으로 쪼갰기 때문에, 가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결할 수 있게 된다.
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)
}
arrSum 함수가 작동하는 방식을 시각적으로 확인해보자.
arrSum
함수가 내부에서 arrSum
함수를 호출하면서 문제가 쪼개어져 나가고, 결국 문제를 더 이상 쪼갤 수 없는 arrSum([])
까지 함수가 호출되는 것을 볼 수 있다.
arrSum([])
는 조건문에 의해 더 이상 자기 자신을 호출하지 않고, 숫자 0을 리턴하면서 종료된다. 그 결과 중첩되어 있던 함수들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.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
을 재귀적으로 구현할 수 있다.
function arrSum(arr) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
if (arr의 길이가 0인 경우) {
return 0;
}
// recursive case : 그렇지 않은 경우
return 요소1 + arrSum([요소2, ... , 요소n]);
}
function recursive(input1, input2, ...) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive case : 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
}