재귀 함수 Recursion

재귀의 정의와 재귀 알고리즘의 기본 규칙을 알아보자.

---

재귀함수 Recursion

재귀함수는 자기 자신을 호출하는 함수를 말하며, 복잡한 문제를 분할 정복 방식으로 해결합니다.

---

스택 오버플로 (Stack OverFlow)

재귀함수를 잘못 구현할 경우 자기 자신을 무한 호출하여 스택 오버플로 (Stack OverFlow)를 초래합니다.

스택 오버 플로 Stack OverFlow
프로그램의 Call Stack에 계속해서 push할 경우 한정된 공간을 초과하게 되는 것을 말합니다.

---

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

재귀함수가 실행되면 함수 실행에 대한 세부 정보를 담고 있는 실행 컨텍스트 (Execution context)가 생성되며 실행 컨텍스트 스택에 쌓이게 됩니다.

재귀의 깊이가 깊어질수록 실행 컨텍스트가 계속 쌓이고 많은 메모리를 차지하게 됩니다.

반복문을 사용한 함수는 하나의 실행 컨텍스트만 스택에 쌓이기 때문에 메모리적인 비용을 고려했을 때는 반복문을 사용하는 것이 효율적일 수 있습니다.

그러나 재귀를 사용한 가독성 좋은 코드와 유지보수를 위해 재귀함수를 사용합니다.

단 재귀함수를 사용할 때 재귀의 깊이를 고려해서 사용되는 메모리를 최소화하는 것이 프로그래밍 성능을 향상시키는 방법입니다.

---

기저 조건

스택 오버플로를 피하기 위해서는 올바른 기저 조건(재귀를 종료하는 조건)을 갖추어야 합니다.

기저 조건을 통과할 때는 재귀함수를 호출하지 않습니다.

// 0 ~ n 숫자 출력
const countNumber = (n) => {
  // 기저 조건 : n 이 0보다 작은 경우
  if (n < 0) {
    return;
  } else {
    console.log(n);
    countNumber(n - 1);
  }
};

countNumber(10);

---

분할 정복 방식

분할 정복 방식이란 어떤 복잡한 문제를 작은 단위로 나누어 해당 문제들을 모두 해결함으로 문제를 해결하는 방식을 말합니다.

위의 예제를 풀어보자면 10 ~ 0 까지 출력하는 큰 문제를 하나를 출력하는 문제들로 나눕니다.

10을 출력한 후 9를 입력으로 문제를 호출합니다.
9를 출력한 후 8을 입력으로 문제를 호출합니다.
…

이런 식으로 분할 정복에 의해 점점 작아지면서 기저 조건에 도달해야합니다.

---

피보나치 수열

피보나치 수열의 n 번째 수는 n-2 번째 수와 n-1 번째 수를 합한 값입니다.

피보나치 수열의 n 번째 수를 출력하는 코드를 작성해보겠습니다.

1. for문

   n 번째 수를 찾기 위해 피보나치 수열의 맨 앞에서부터 추적해나갑니다.

   const getNthFibo = (n) => {
     if (n <= 1) return n;
   
     var sum = 0,
       last = 1,
       lastlast = 0;
   
     for (let i = 0; i < n; i++) {
       sum = last + lastlast;
       lastlast = last;
       last = sum;
     }
   
     return sum;
   };
   

2. 재귀 함수

   기저 조건 : n이 1일 때
   분할 정복 : N-1 번째 피보나치 수 + N-2 번째 피보나치 수

   const getNthFibo = (n) => {
     if (n <= 1) return n;
     else {
       return getNthFibo(n - 2) + getNthFibo(n - 1); // return 문에 + 연산자 존재 일반 재귀
     }
   };
   

   해당 코드는 시간 복잡도가 O(2^n) 입니다. 이를 줄이기 위해 꼬리 재귀를 사용해보겠습니다.

---

꼬리 재귀 (Tail Recursion)

꼬리 재귀는 재귀 호출이 함수에서 마지막에 실행되는 방식의 재귀를 말합니다.

재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는 방법으로 return문에 함수이외의 연산자나 값을 사용하지 않습니다.

이 방식을 사용하게 되면 이전 함수의 상태를 유지하지 않고 추가 연산을 하지 않기 때문에 스택이 넘쳐나는 문제를 해결할 수 있습니다.

const getNthFibo = (n, last = 1, lastlast = 0) => {
  if (n == 0) return lastlast;
  if (n == 1) return last;

  return getNthFibo(n - 1, lastlast + last, last); // return문에 함수만 존재 꼬리 재귀
};

해당 코드는 시간 복잡도가 O(n) 입니다.

---

결론

메모리는 for문을 사용하는 것이 효과적이지만 재귀함수는 가독성이 좋아 유지보수를 위해 필요합니다.

꼬리 재귀 등의 방법으로 시간 복잡도를 줄여 메모리를 아끼고 스택오버플로를 방지할 수 있습니다.