재귀함수 추가학습

 

재귀 함수와 메모리 사용량 간의 관계

 

자바스크립트 엔진은 최대 재귀 깊이를 제한

(만개 정도까진 확실히 허용하고, 엔진에 따라 이보다 더 많은 깊이를 허용하는 경우도 있다

하지만 대다수의 엔진이 십만까지는 다루지 못한다.)

재귀 깊이 제한 때문에 재귀를 실제 적용하는데 제약

 

 

요약해보기

-> 재귀 함수는 반복적으로 자신을 호출 하기 때문에 스택이라는 메모리가 쌓인다.
이때, 스택이 많이 쌓이게 된다면 에러가 발생한다. -> '스택 오버 플로우' 현상

 

 

꼬리재귀 (Tail Recursion)

재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는 방법

이전 함수의 상태를 유지하지도 않고 추가 연산을 하지도 않아서 스택이 넘쳐나는 문제를 해결

//일반 재귀

function factorial(n) {
    if (n === 1) {
        return 1;
    }
    return n * factorial(n-1);
}

// console.log (factorial(4))
// factorial(4) = 4 * factorial(3)
// factorial(3) = 3 * factorial(2)
// factorial(2) = 2 * factorial(1)
// factorial(1) = 1
// 24

//꼬리 재귀
function factorial(n, total = 1){
    if(n === 1){
        return total;
    }
    return factorial(n - 1, n * total);
}

// console.log (factorial(4, 1))
// 24

 

요약해보기

->  일반 재귀는 함수를 재 호출하면서 하나씩 쌓아가는 반면,
꼬리 재귀는 결과값을 바로 전달하여 반환

 

 

하노이의 탑

 

 

하노이의 탑은 (Tower of Hanoi) 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 문제

'작은 원반 위에 큰 원반을 올릴 수 없다'

재귀함수의 좋은 예

결론적으로 n개의 원판을 다른 쪽으로 옮기는 데 걸리는 최소 횟수는 2ⁿ-1

 

let count = 0

const hanoi = (num, from, to, sub) => { // 원판갯수, 출발, 목적, 보조 
  if (num === 0) return
  hanoi (num - 1, from, sub, to)
  console.log(`${num}번 원판을 ${from}번에서 ${to}로 옮긴다.`)
  count++
  hanoi (num - 1, sub, to, from)
  return count
}

hanoi(3, 'a', 'b', 'c') // 2^3-1 ==> 7

 

요약해보기

->  재귀함수의 좋은 예