본 포스팅은 Colt Steele의 JavaScript 알고리즘 & 자료구조 마스터클래스를 수강하며 정리한 노트입니다.
https://www.udemy.com/course/best-javascript-data-structures/
42. 재귀함수를 사용하는 이유
재귀는 자기자신을 호출하는 함수를 의미한다.
A process (a function in our case) that calls itself.
재귀 함수는 이미 많은 곳에서 쓰이고 있음.
- JSON.parse나 JSON.stringify의 소스코드에도 내부에서 재귀가 사용되고 있다.
- document.getElementById같은 DOM을 순회하는 알고리즘
- 객체 순환
때로는 반복보다 재귀를 사용하는 것이 깔끔할 때도 있다.
43. 스택호출하기
함수는 보통 순서대로 실행되기 마련. 이를 호출 스택이라고 함.
호출스택은 자바스크립트의 보이지 않는 곳에서 작동하는 정적 데이터 구조(static data structure).
함수를 호출하면, 책상 위에 쌓인 종이더미의 맨 위에 쌓이듯 스택의 꼭대기 위에 쌓임.
개발자 도구의 source탭에 들어가면 콜스택을 분석하기 편함.
그러나 일반적인 재귀함수는 계속해서 자기자신을 호출하며 어떤 시점에서는 종료해야한다.
44. 첫번째 재귀 함수
기본 개념: 동일한 함수를 계속 호출하면서, 하나의 함수가 자기자신을 재귀적으로 호출하게 하는 것.
재귀 함수를 이루는 필수요건 두가지:
1. 종료조건: 재귀가 끝나는 시점. 루프에 걸리지 않아야함.
2. 다른 입력값: 매번 다른 데이터를 가지고 함수를 호출해야 함.
function countDown(num) {
if(num <= 0) {
console.log("All done!");
return;
}
console.log(num);
num--;
countDown(num);
}- 종료조건: num이 0일 때 return을 해줌.
- 다른 입력값: 1씩 줄어드는 num.
위 함수를 실행시킬 경우 5, 4, 3, 2, 1이 출력된 후 All done!이 출력될 것.
45.
function sumRange(num) {
if(num === 1) {
return 1;
}
return num + sumRange(num - 1);
}- 종료조건: num이 1일 경우 1을 return
- 다른 입력값: 1씩 줄어드는 num.
sumRange(3);
return 3 + sumRange(2);
return 2 + sumRange(1);
return 1;
최종적으로 sumRange(3)이 리턴하는 값은 6.
sumRange가 콜스택에 잔뜩 쌓여서 아래로 차례차례 결과 값을 리턴해주는 모양새.
46. 재귀함수로 팩토리얼 구성하기
10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
위와 같은 수식을 팩토리얼이라고 함.
아래는 비재귀적인 반복적 솔루션
function factorial(num) {
let total = 1;
for (let i = num; i > 1; i--) {
total *= i;
}
return total;
}아래는 재귀적 솔루션
function factorial(num) {
if (num === 1) {
return 1;
}
return num * factorial(num - 1);
}콜스택이 쌓이고, 하나씩 해소되면서 아래쪽 콜에 곱하기 결과를 1부터 시작해 차례차례 return.
결과적으로 팩토리얼 곱하기의 연속이 가능해짐.
48. 통상적인 재귀의 잠재적 위험
- 종료조건: 종료조건이 없을시 빠져나가지 못함.
function factorial(num) {
//if (num === 1) {
// return 1;
//}
return num * factorial(num - 1);
}- 종료조건2: 종료시 return을 해주지 않을 때.
function factorial(num) {
if (num === 1) {
//return 1;
}
return num * factorial(num - 1);
}- 다른 입력값: 실수로 같은 값을 계속 함수에 대입.
function factorial(num) {
if (num === 1) {
return 1;
}
return num * factorial(num); // num - 1가 아니고?!
}infinite loop에 빠지며 maximum call stack size exceeded가 뜨게 됌.
return이 중요한 이유는 재귀의 토대가 되기 때문.
호출 스택이라는 개념은 모든 항목이 서로에게 의존하면서 계속 기다린다는 것.
띠 처럼 연결된 것이기 때문에 return이 매우 중요함.
chrome에서는 최대 호출 스택 크기 초과가 뜨며 이를 stack overflow라고 함.
49. Helper 메소드 재귀
배열이나 데이터 목록 같은 걸 컴파일해야할 때 흔히 메인 함수 내부에서 헬퍼재귀함수를 작성함.
function collectOddValues(arr) {
let result = [];
function helper(helperInput) {
if (helperInput.length === 0) {
return;
}
if (helperInput[0] % 2 !== 0) {
result.push(helperInput[0])
}
helper(helperInput.slice(1)); //맨 앞을 지워가며 다시 [0]를 검사. 홀수일 때만 result에 push.
}
helper(arr);
return result;
}result를 재귀함수 안에 정의하면 함수가 호출될 때마다 빈 배열로 리셋되기 때문에,
바깥에 위치한 메인 함수안에 빈 배열을 정의하고 같은 레벨에 핼퍼재귀함수를 작성해서 push하도록 함.
50. 순수재귀
순수 재귀의 경우 필요한 모든 코드가 함수 자체에 포함되며 재귀적임.
외부에 선언된 빈 result 배열등을 쓰지 않음.
function collectOddValues(arr) {
let newArr = [];
if (arr.length === 0) {
return newArr;
}
if (arr[0] % 2 !== 0) {
newArr.push(arr[0]);
}
newArr = newArr.concat(collectOddValues(arr.slice(1)));
return newArr;
}
collectOddValues([1, 2, 3, 4, 5]); //실행아래처럼 콜스택이 쌓이고 해소되면서 차곡차곡 concat됌.
[1].concat(collectOddValues([2, 3, 4, 5]))
[].concat(collectOddValues([3, 4, 5]))
[3].concat(collectOddValues([4, 5]))
[].concat(collectOddValues([5]))
[5].concat(collectOddValues([]))
[]배열을 복사하는 slice, spread, concat과 같은 메소드를 이용하면 배열을 mutate할 필요가 없음.
그러면 일종의 결과를 축적할 수가 있음.
그러나 string은 immmutable. slice나 substring을 사용해서 사본을 만들어야 함.
객체의 경우, Object.assign이나 spread 연산자를 사용하는 게 유용.
핼퍼재귀함수가 더 "직관적"이긴 하지만 물론 위와 같이 순수재귀를 통해서도 문제해결 가능.
