함수를 호출하면 stack에 execution context(실행 컨텍스트)가 배치된다.
재귀에서 stack에 배치된 실행 컨텍스트는 다른 실행 컨텍스트에서 오는 반환 값을 기다리고 있다. 스택의 마지막 항목이 실행을 마치면 해당 컨텍스트는 반환 값을 생성한다. 이 반환 값은 다음 실행 컨텍스트에 반환 값으로 전달된다. 그런 다음 해당 실행 컨텍스트는 스택에서 제거된다.
const factorial = function(num) {
debugger;
if (num === 0 || num === 1) { // base case
return 1;
} else {
return num * factorial(num - 1); // recursive case
}
};
factorial(5);
5
를 사용하는 factorial()이 배치된다. base case가 false 이므로 다시 재귀 함수를 실행한다.num-1(5-1) = 4
를 사용하는 factorial()이 배치된다. base case가 false이므로 다시 재귀 함수를 실행한다.num-1(4–1) = 3
를 사용하는 factorial()이 배치된다. base case가 false 이므로 다시 재귀 함수를 실행한다.num-1(3–1) = 2
를 사용하는 factorial()이 배치된다. base case가 false이므로 다시 재귀 함수를 실행한다.num-1(2–1) = 1
를 사용하는 factorial()이 배치된다. base case가 true 이므로 1을 반환한다.아래의 그림에 표현이 잘 되어있어서 가져왔다. Good ~ 👍👍👍
이미지 출처 : freeCodeCamp
재귀는 매우 깔끔하다.
for 또는 while 루프를 사용하여 동일한 작업을 수행 할 수 있다. 그러나 재귀를 사용하면 더 읽기 쉬운 우아한 솔루션을 얻을 수 있기 때문에 우리는 재귀 솔루션을 사용한다.
여러 번 작은 문제로 분류 된 문제가 더 효율적이다. 문제를 더 작은 부분으로 나누면 문제를 극복하는 데 도움이된다. 따라서 재귀는 문제를 해결하기위한 분할 및 정복 방식이다.
const fibonacci = function(num) {
if (num <= 1) {
return num;
} else {
return fibonacci(num - 1) + fibonacci(num - 2);
}
};
fibonacci(5);
function flatten(arr) {
let result = [];
arr.forEach(elem => {
if (!Array.isArray(elem)) {
result.push(elem);
} else {
result = result.concat(flatten(elem));
}
});
return result;
}
flatten([1, [2], [3, [[4]]]]);
function reverse(str) {
if (str.length === 0) {
return "";
}
return str[str.length - 1] + reverse(str.substr(0, str.length - 1));
// str의 마지막 문자 + reverse(str의 마지막을 제외한 문자)
}
reverse('banna'); // annab
function searchArraySequentially(array, i, j, x) {
if (i <= j) {
if (array[i] === x) { // base case
return i;
} else { // recursive case
return searchArraySequentially(array, i + 1, j, x);
}
} else { // base case
return -1;
}
}
var array = ['a', 'b', 'c', 'd', 'e'];
var result1 = searchArraySequentially(array, 0, 4, 'e');
var result2 = searchArraySequentially(array, 0, 3, 'e');
console.log(result1); // 4;
console.log(result2); // -1;