재귀 함수
재귀 함수란?
재귀 함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다.
사용 방법
function sumTo(num) {
if(num === 0) {
return 0;
}
return num + sumTo(num - 1);
}언제 사용해야 할까?
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수(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);
}
}
}
}
}
}
}
}모든 재귀 함수는 반복문으로 표현할 수 있다. 하지만 위의 예시처럼 for문의 중첩이 많아지면 가독성이 떨어진다. 이럴 때 재귀를 적용하면 코드가 더욱 간결하고 이해하기 쉬워진다.
재귀적 사고 연습하기
재귀적 사고를 기르는 방법은 무조건 반복해서 풀어보는 것이다.
언어를 배우는 것처럼 자연스러워질 때까지 연습해야한다.
- 재귀 함수의 입력값과 출력값 정의하기
재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 됩니다. 재귀적으로 사고하는 데에 가장 먼저 해야할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것이다. 함수 arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴한다. 이를 좀더 간단하게 표기하면 다음과 같다.
arrSum: [number] => number
- 문제를 쪼개고 경우의 수를 나누기
주어진 문제를 어떻게 쪼갤 것인지 고민한다. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다. 일반적인 경우, 입력값으로 이 기준을 정한다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기이다. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다. 그리고 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같다면, 문제를 제대로 구분한 것이다.
- 함수
arrSum의 경우 입력값인 리스트(배열)의 크기에 따라, 더 작은 문제로 나눌 수 있다. 그리고arrSum([1, 2, 3, 4])를 구하는 방법과arrSum([2, 3, 4])을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.
이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눈다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눕니다.
-
함수
arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 각각의 경우는 다른 방식으로 처리해야 한다. -
arrSum: [number] => number
arrSum([ ])
arrSum([e1, e2, ... , en])
- 단순한 문제 해결하기
문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)이라고 부른다. 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.
-
함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0이다.
-
arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en])
- 복잡한 문제 해결하기
남아있는 복잡한 경우를 해결한다.
-
길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 정할 것이다.), 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결하여 얻은 결과를 head에 더한다.
-
arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en]) -
배열을
head와 나머지 부분(tail)으로 구분하는 방법만 안다면, 함수 arrSum을 재귀적으로 구현할 수 있다.
- 코드 구현하기
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, ...)
}