TIL 6주차 - 2. 재귀함수

재귀함수

자신을 다시 호출하는 재귀함수는 다음 상황에서 적합하다.

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

재귀함수는 함수 내에서 자신을 호출한 후 그 함수가 끝날 때까지 재귀 함수 호출 이후의 명령문이 수행되지 않으며, 반드시 종료 조건을 포함해야한다.

재귀함수 사용 이유

재귀함수 사용 이유는 다음과 같다.

1. 간결하고 이해하기 쉽다.
2. 알고리즘 자체가 재귀적인 표현이 자연스러운 경우
3. 변수 사용을 줄일 수 있다.

변수 사용을 줄여준다는 것은 변수가 잡는 메모리가 아니라,
mutable state (변경 가능한 상태)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 것이다.

재귀호출이 직관적으로 이해하기 어려울 수 있지만, 프로그램이 복잡해지면 mutable state를 최대한 피하는 것이 오류 없는 프로그램을 짜는데 중요한 원칙이 된다.

나의 생각

for문은 단반향적이고, 완전탐색과 같은 경우 구현하는데 한계가 있는 것 같다.

재귀를 사용하면 마지막 노드에 도달할 때 이전 노드로 돌아갈 수 있고, 그 구현이 for문으로 구현하는 것보다 훨씬 짧은 코드구현과 가독성이 좋다.

재귀함수 단점

하지만, 재귀함수는 메모리를 많이 차지하고 성능이 반복문에 비해 느리다.

함수 호출 시 함수의 매개변수, 지역변수, 리턴 값 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장된다.
현재 실행중인 함수가 끝나지 않은 채로 새로운 함수를 호출하므로 함수의 스택 프레임(실행 컨텍스트)이 콜 스택에 쌓이게 된다. 이는 스택 오버플로우가 발생할 수 있는 위험성이 있으며 재귀의 중첩의 정도(recursion depth)가 깊어질수록 메모리를 차지하는 단점이 있다.

이러한 기존 재귀의 문제점을 해결할 수 있는 방법은 없을까??

꼬리재귀가 해결방법이 된다고 한다.

해당 내용은 여기로 재귀함수 plus

---

피보나치 수열

function fibonacci(num) {
  if (num === 0) return 0;
  if (num === 1) return 1;
  return fibonacci(num - 2) + fibonacci(num - 1);
}

let output = fibonacci(5);
console.log(output); // --> 5

피보나치 수열 재귀함수 효율성

위와 같이 피보나치 수열을 계산하면 효율성이 떨어지는 것을 확인할 수 있다.

트리를 보면 확인할 수 있듯이, f(0)은 3번, f(1)은 5번이 호출되었다. 만약 더 큰 수를 계산하게 된다면 반복되는 호출은 더욱 많아지게 된다.
(O(n^2)의 시간복잡도를 가지게 된다.)

아래와 같이 재귀함수를 사용하면서 재귀함수의 비효율을 줄이는 코드를 작성할 수 있다.

내 코드

function fibonacci1(n) {
  let arr = [0, 1];

  if (n <= 1) {
    return arr[n];
  }

  function repeat(num) {
    if (num === 0) {
      return arr[arr.length - 1];
    }

    let next = arr[arr.length - 2] + arr[arr.length - 1];
    arr.push(next);
    return repeat(num - 1);
  }

  return repeat(n - 1);
}

레퍼런스

let fibonacci = function (n) {
  const memo = [0, 1];
  const aux = (n) => {
    // 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.

   if (memo[n] !== undefined) return memo[n];
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.

   memo[n] = aux(n - 1) + aux(n - 2);
    return memo[n];
  };
  return aux(n);
};

참고)
https://kldp.org/node/134556