재귀란?
함수를 스스로 호출하는 것을 말한다.
function foo() {
foo();
}재귀는 언제 사용하는게 좋을까?
재귀는 특히 아래와 같은 상황에서 매우 적합하다.
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);
}
}
}
}
}
}
}
}사실 모든 재귀 함수는 재귀 호출 없이 while / for loop으로 표현이 가능하다.
하지만 재귀를 사용 가능한 경우, 재귀를 사용한 코드가 대부분의 경우 더욱 간결하고 일부의 경우에는 이해하기도 쉽다.
재귀적으로 사고하기
1 . 재귀 함수의 입력값과 출력값 정의하기
재귀 함수를 통해 어떤 문제를 풀고자 하는지, 즉 우리의 목표를 정리하는 데 도움이 된다.
문제를 가장 추상적으로 또는 가장 단순하게 정리하는 것이다.
arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받아서 number를 리턴한다.
이를 좀더 간편하게 아래와 같이 표기한다고 가정해보자.
arrSum: [number] => number2 . 문제를 쪼개고 경우의 수를 나누기
주어진 문제를 어떻게 쪼갤 것인지 고민한다.
어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 검토해본다.
일반적으로 입력값이 이 기준을 정하는 대상이 된다.
이 때 중요한 관점은 순서와 크기이다.
주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나, 순서를 명확하게 정할 수 있는지를 살펴보는 것이 도움이 된다.
그리고 구분된 문제들을 푸는 방식이 같다면, 문제를 제대로 구분한 것이다.
arrSum의 경우 입력값인 배열을 크기에 따라 구분할 수 있다.
그리고 arrSum([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])을 구하는 방법은 동일할 것이므로 이 구분은 적절하다고 판단할 수 있다.
이제 문제의 입력값에 따라 경우의 수를 나눈다.
일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.
arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다.
각각의 경우는 다르게 처리되어야 한다.
arrSum: [number] => number
arrSum([ ])
arrSum([e1, e2, ... , en])3 . 단순한 문제 해결하기
문제를 여러 경우로 구분한 다음에는 쉬운 문제부터 해결한다.
이를 재귀의 기초(base case)라고 한다.
재귀의 기초는 나중에 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게 된다.
arrSum를 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이 때 arrSum은 0이다.
arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en])4 . 복잡한 문제 해결하기
남아있는 복잡한 경우를 해결한다.
arrSum이 길이가 1 이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이겠다.), 나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더한다.
arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])배열이 있을 때 head와 나머지 부분(tail)을 구분하는 방법만 안다면, arrSum을 해결할 수 있다.
5 . 코드 구현하기
function arrSum(arr) { // 재귀의 기초 (base case) // 문제를 더 이상 쪼갤 수 없을 경우 if (arr의 길이가 0인 경우) { return 0; } // recursive Case // 그렇지 않은 경우 // head: 배열의 첫 요소 // tail: 배열의 첫 요소만 제거된 배열 return head + arrSum(tail); }
아래는 일반적인 재귀 함수의 템플릿이다.
function recursive(input1, input2, ...) { // 재귀의 기초 (base case) if (문제를 더 이상 쪼갤 수 없을 경우) { return 단순한 문제의 해답; } // recursive Case // 그렇지 않은 경우 return 더 작은 문제로 새롭게 정의된 문제 // 예1. someValue + recursive(input1Changed, input2Changed, ...) // 예2. someValue * recursive(input1Changed, input2Changed, ...) }
