2.5Recursion-Theory

What is recursion?

A process that calls itself Recursion(재귀)은 함수가 자기 자신을 호출(self-call)하는 과정을 말한다.
간단하지만 강력한 개념으로, 반복문보다 더 명확하고 직관적인 해결책을 제공하는 경우가 많다.

Why use recursion?

• 우리가 자주 사용하는 함수들 내부에서 사용된다:
  • JSON.parse, JSON.stringify
  • document.getElementById
  • DOM 트리 순회, 중첩 객체 탐색 등
• 복잡한 반복문보다 더 선언적이고 간결한 표현 가능
• 특정한 구조(트리, 그래프, 중첩 구조)에 특히 적합

The Call Stack

• 자바스크립트는 단일 스레드이며, 함수 호출은 Call Stack 위에 쌓인다.
• 스택(Stack) 자료구조: LIFO(Last In First Out)
• 함수가 호출되면 push, 종료되면 pop된다.
• return 키워드를 만나면 현재 함수는 종료되고, 이전 스택으로 돌아간다.

브라우저 개발자 도구의 Sources 탭에서 Breakpoint를 걸면 해당 시점에서의 Call Stack을 확인 가능하다.

재귀 함수의 필수 조건 2가지

1. Base Case: 종료 조건
2. Different Input: 반복마다 입력이 변해야 한다. 종료 조건을 향해 간다.

예를 들어, 아래 countDown 함수에선

1. Base Case: num <= 0이 되면 끝난다.
2. Different Input: 입력값인 num이 계속 1씩 감소하고 다시 자신을 호출한다.

javascript
function countDown(num){
  if(num <= 0){
    console.log('All done!')
    return;
  }
  console.log(num);
  num--;
  countDown(num)
}

또 다른 예시도 살펴보자. 아래는 입력값까지 더하는 함수다:

1. Base Case: num === 1
2. Different Input: num을 계속 1씩 줄인다.

javascript
function sumRange(num){
  if(num === 1) return 1;
  return num + sumRange(num - 1);
}

javascript
function factorial(num){
  if(num === 0) return 1;
  if(num === 1) return 1;
  return num * factorial(num - 1);
}

재귀 함수를 쓸 때 가장 자주 틀리는 부분

• Base Case가 없음 → 무한 재귀 → Maximum call stack size exceeded
  • Stack Overflow 현상이라고 한다.
• return을 잊거나 잘못 작성 → 역시나 스택 오버플로우가 발생한다.

Helper Method Recursion

재귀 내에서 배열 등에 값을 누적해야 할 때, 외부 변수(result)를 재귀 안에서 계속 초기화하면 누적되지 않는다.

이럴 때 주 함수 안에 일종의 보조 함수, 즉 Helper 함수를 쓰는 식으로 해결할 수 있다. 예를 들어, 입력받은 배열의 홀수만 모은 배열을 반환하는 함수를 쓴다고 하자.

javascript
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))
  }
  helper(arr)

  return result;
}

하지만, 위와 같은 보조 함수의 도움 없이도 해결할 수 있다. Pure Recursion 방식이라고 하는데, 원본을 변형하지 않기 위해 아래의 복사 방법을 활용한다:

• 배열 복사: slice, concat, ...
• 문자열 복사: slice, substring
• 객체 복사: Object.assign, ...

javascript
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;
}

쉬운 예시 1: power

밑과 지수를 받아 계산해주는 power함수를 작성하라.

javascript
function power(base, exponent){
    if(exponent === 0) return 1;
    return base * power(base, exponent -1);
}

쉬운 예시 2: fib

숫자를 받아, 해당 숫자에 해당하는 피보나치 수를 구해주는 fib 함수를 작성하라. (피보나치 수는, 이전 두 개의 수를 더했을 때 나오는 수다. 1, 1, 2, 3, 5, ...)

javascript
function fib(n){
  if(n === 1 || n === 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

---

🤠 개인 탐구

피보나치 수열 함수 개선

앞선 방식은 중복 호출이 많아 시간 복잡도가 무려 O(2ⁿ)에 이른다.

이를 개선하는 방식에 대해 알아보니, 크게 두 가지 방법이 있다.

1. Memoization - Top-Down 방식

이미 계산한 값을 캐싱하는 방식이다. 앞서 본 방식은 한 피보나치 수를 구하는 두 개의 이전 피보나치 수를 구하기 위해 계속 가지를 치는데, 이러다보면 한번 계산했던 수를 또 계산하게 된다.

예를 들어, fib(5)를 계산하면 아래와 같은 상황이 벌어진다:

text
fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  └─ fib(1)
│  └─ fib(2) ← ⚠️ 중복
└─ fib(3) ← ⚠️ 중복
   ├─ fib(2)
   └─ fib(1)

이럴 때, 자바스크립트 객체를 통해 한번 계산한 수는 저장했다가 해당 피보나치 수는 바로 반환하면 성능이 O(n)으로 개선된다. O(n)인 이유는 n까지의 수들이 모두 딱 1번씩만 계산되기 때문이다.

javascript
function fib(n, memo = {}) {
  if (n <= 2) return 1;

  if (memo[n]) return memo[n];

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

2. Tabulation(테이블 방식) - Bottom-Up 방식

반복문을 사용해 작은 값부터 차례로 계산해나가는 방식이다. 이 방식은 재귀를 사용하지 않고 시간 복잡도를 O(n)으로 줄인다.

javascript
function fib(n) {
  if (n <= 2) return 1;

  const fibTable = [0, 1, 1]; // index i와 피보나치 수 순서 n을 일치 시키기 위한 0번째 인덱스

  for (let i = 3; i <= n; i++) {
    fibTable[i] = fibTable[i - 1] + fibTable[i - 2];
  }

  return fibTable[n];
}