1. 재귀(Recursion)란?
- 재귀(Recursion)란 동일한 함수를 계속 호출하면서, 하나의 함수가 자기 자신을 재귀적으로 호출하는 함수를 의미한다.
2. 재귀 함수의 기본 요소
1) Base Case
- Base Case는 재귀가 멈추는 시점(종료 조건)이다.
2) Recursive Case
- Recursive Case는 재귀 함수 실행으로 더 작은 문제로 새롭게 정의된 input을 받아 다시 재귀 함수를 호출하는 부분이다.
// 1. num을 입력받으면 최초 num을 한 번 출력하고 1을 뺀 후 다시 countDown 함수를 호출한다.
// 2. 그럼 num - 1 값을 출력하고 다시 1을 뺀 후 다시 countDown 함수를 호출한다.
// 3. 위 과정을 계속 반복하다가 num이 0보다 작거나 같아지면 함수를 종료한다.
function countDown(num) {
// Base Case
if (num <= 0) {
console.log("Done!"); // Done!
// Recursive Case
} else {
console.log(num); // 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
num--;
countDown(num);
}
}
console.log(countDown(10));3. 재귀 함수의 동작 순서
1) 1 부터 num까지의 숫자 합 구하기
- 아래 예제에서 num을 입력받았을 때 num과 num - 1을 더하는 과정을 num이 1이 될 때 까지 반복한다.
- sumTo(5) = return 5 + sumTo(4)
- sumTo(4) = return 5 + 4 + sumTo(3)
- sumTo(3) = return 5 + 4 + 3 + sumTo(2)
- sumTo(2) = return 5 + 4 + 3 + 2 + sumTo(1) === 1
-
sumTo(5)는 sumTo(4)에 5를 더하려고 하는데 sumTo(4)가 아직 계산이 되지 않아 값을 모르므로 콜 스택에 대기하고 있는다. sumTo(3), sumTo(2)도 마찬가지로 콜 스택에서 대기중인 상태이다.
-
sumTo(1)은 1을 반환하므로 재귀에서 탈출하게 된다. 그러고 나면 호출 스택에서 모든 값이 반대 순서로 합산되어 결과적으로 1부터 num까지의 합을 구하게 된다.
// 1. num을 입력받으면 입력받은 num값과 num - 1값을 더하는 과정을 num이 1이 될 때 까지 반복한다.
// 2.
function sumTo(num) {
// Base Case
if (num <= 1) { // num이 1보다 작거나 같을 때
return num; // 1
// Recursive Case
} else {
return num + sumTo(num - 1); // 55
}
};
2) 배열의 모든 요소의 곱 구하기
- 동작 과정(productOfArray([1, 2, 3])을 입력받은 경우)
- 1 * productOfArray([2, 3])
- 1 2 productOfArray([3]) -> arr.length가 1인 경우 3을 리턴하므로 역으로 계산된다.
function productOfArray(arr) {
// Base Case
if (arr.length === 1) {
return arr[0];
// Recursive Case
} else {
return arr[0] * productOfArray(arr.slice(1));
}
}3) 팩토리얼 구하기
- 동작 과정(factorial(4)를 입력받은 경우)
- 4 * factorial(3)
- 4 3 factorial(2)
- 4 3 2 * factorial(1) -> num이 1인 경우 1을 리턴하므로 역으로 계산된다.
function factorial(num) {
// Base Case
if (num <= 1) {
return num;
// Recursive Case
} else {
return num * factorial(num - 1);
}
}4) 피보나치 수열
- 동작 과정(fib(10)을 입력받은 경우)
- fibonacci(0) = 0
- fibonacci(1) = 1
- fibonacci(2) = 0 + 1 = 1 -> fibonacci(0) + fibonacci(1)
- fibonacci(3) = 1 + 1 = 2 -> fibonacci(1) + fibonacci(2)
- fibonacci(4) = 1 + 2 = 3 -> fibonacci(2) + fibonacci(3)
- fibonacci(5) = 2 + 3 = 5 -> fibonacci(3) + fibonacci(4)
- fibonacci(6) = 3 + 5 = 8 -> fibonacci(4) + fibonacci(5)
- fibonacci(7) = 5 + 8 = 13 -> fibonacci(5) + fibonacci(6)
- fibonacci(8) = 8 + 13 = 21 -> fibonacci(6) + fibonacci(7)
- fibonacci(9) = 13 + 21 = 34 -> fibonacci(7) + fibonacci(8)
- fibonacci(10) = 21 + 34 = 55 -> fibonacci(8) + fibonacci(9)
function fib(num) {
if (num <= 1) {
return num;
} else {
return fib(num - 2) + fib(num - 1);
}
}4. Helper 메서드 재귀
-
Helper 메서드 재귀는 재귀적이지 않은 외부 함수가 재귀적인 내부 함수를 호출하는 패턴을 말한다.
-
result를 함수 안에 호출하고 재귀를 실행하면 재귀가 실행될 때 마다 result는 초기화 되기 때문에 값을 담을 수 없다. 따러서 재귀 함수 내에 또 하나의 helper 함수에 재귀를 실행시키고 result는 helper 함수 밖에 호출하여 초기화 되지 않고 result에 계속 데이터가 담기도록 한다.
function oddValue(arr) {
let result = [];
function helper(helperInput) {
// Base Case
if (helperInput.length === 0) {
return;
} else if (helperInput[0] % 2 !== 0) {
result.push(helperInput[0]);
}
// Recursive Case
helper(helperInput.slice(1));
}
// 처음 oddValue 함수가 호출되면 helper를 건너뛰고 바로 helper(arr)가 실행된다.
helper(arr);
return result;
}
console.log(oddValue([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])); // [1, 3, 5, 7, 9]-
아래는 helper 메서드 재귀를 사용하지 않고 순수 재귀로만 구현한 동일한 함수다.
-
실행 과정은 아래와 같다. 아래의 과정을 arr.length가 0이 될 때까지 반복하다가 0이 되면 newArr에 구해놨던 배열을 역으로 다시 합친다.
- arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], newArr = [1]
- arr = [2, 3, 4, 5, 6, 7, 8, 9, 10], newArr = empty array
- arr = [3, 4, 5, 6, 7, 8, 9, 10], newArr = [3]
- arr = [4, 5, 6, 7, 8, 9, 10], newArr = empty array
...
function pureValue(arr) {
let newArr = [];
// Base Case
if (arr.length === 0) {
return newArr;
} else if (arr[0] % 2 !== 0) {
newArr.push(arr[0]);
}
// Recursive Case
newArr = newArr.concat(pureValue(arr.slice(1)));
return newArr;
}
console.log(pureValue([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])); / [1, 3, 5, 7, 9]