재귀 함수

🤓오늘의 공부 주제: 재귀함수🤓

재귀란?
재귀는 어떤것을 정의할때 자기 자신을 참조하는 것을 뜻한다.

콜스택:함수가 호출되면서 올라가는 메모리 영역.스택이라고도 불림. 스택은 first in first out

함수를 호출하면 콜스택에 올라가고 함수가 종료되면 콜스택에서 제거.
재귀함수는 호출할때마그 콜스택 영역을 차지. for문으로 해결할 수 있는 작업을 재귀함수쓰면 비효율적.

재귀함수를 활용하는 대표적예시가 팩토리얼.1부터n까지의 곱

function sumArray(arr){
    if(arr.length == 1) return arr[0];
    return sumArray(arr.slice(0, -1)) + arr[arr.length -1];
}

let arr = [1,2,3,4,5];
let sum = sumArray(arr);
console.log(sum);

function power(x, n){
    if(n == 0) return 1;
    return power(x, n - 1) * x;
}

console.log(power(2, 5));

function strLength(arr){
    if(arr[0] == null) return 0;
    return strLength(arr.slice(0, -1)) + 1;
}

let str = "abcde";
let len = strLength(str);
console.log(len);

✍️재귀함수 패턴

1.단순 반복 실행. for 문으로 대체 가능. 콜스택 성능 비효율.
2. 하위문제의 결과를 기반으로 현재 문제 계산. for문 사용은 상향식 계산. 재귀는 하향식 계산(모든 재귀가 하향식은 아님)상향식 재귀는 for문으로 대체 가능. 그러나 하향식 재귀는 오직 재귀함수로만 구현.

💡재귀함수 만드는 꿀팁: 앞의 문제가 해결됐다고 가정하고 접근.

재귀 함수의 꽃 하노이의 탑🌼

function hanoi(count, from, to, temp){
    if(count == 0) return;
    hanoi(count - 1, from, temp, to);
    console.log(`${count} ${from} -> ${to}`);
    hanoi(count - 1, temp, to, from);
}

hanoi(3, "A", "C", "B");