재귀 (Recursion)

계산 중... 0
Computer Science Algorithms Programming Concepts
Recursion Algorithm Programming

거울 앞에 거울을 두면 무한히 반복되는 이미지를 본 적 있나요?

이것이 바로 재귀라고 할 수 있습니다!

처음 재귀를 접했을 때는 “무한 루프가 아닌가?”라는 생각이 들었습니다. 하지만 실제로 사용해보니, 수십 줄의 반복문이 단 몇 줄의 재귀 함수로 간결하게 바뀌더라고요.

왜 재귀를 배워야 할까요?

1. 코드를 훨씬 짧고 읽기 쉽게 작성할 수 있습니다

// 반복문으로 팩토리얼
function factorialLoop(n) {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

// 재귀로 팩토리얼
function factorialRecursive(n) {
  if (n <= 1) return 1;
  return n * factorialRecursive(n - 1);
}

// 4줄이 2줄로! 🎯

2. 특정 문제는 재귀가 훨씬 자연스럽습니다

  • 트리 탐색 (폴더 구조, DOM)
  • 그래프 탐색 (DFS)
  • 분할 정복 알고리즘 (병합 정렬, 퀵 정렬)
  • 백트래킹 (미로 찾기, 순열 조합)

3. 많은 알고리즘의 기초가 됩니다

재귀를 이해하면 다음을 배우기 쉽습니다.

  • 동적 프로그래밍
  • 그래프 알고리즘 (DFS, BFS)
  • 분할 정복 알고리즘

먼저, 기초부터 이해하기

재귀란 무엇인가?

재귀(Recursion)는 함수가 문제를 해결하기 위해 자기 자신을 호출하는 프로그래밍 기법입니다.

핵심은 두 가지입니다:

  1. 기저 조건 (Base Case): 재귀를 멈추는 조건
  2. 재귀 호출 (Recursive Case): 문제를 더 작게 만들어 자신을 호출
function recursiveFunction(n) {
  // 1. 기저 조건: 재귀를 멈춤
  if (n <= 0) {
    return "종료!";
  }

  // 2. 재귀 호출: 문제를 작게 만들어 자신을 호출
  return recursiveFunction(n - 1);
}

왜 동작할까요?

재귀가 동작하는 원리는 콜 스택(Call Stack)입니다.

function countdown(n) {
  if (n <= 0) {
    console.log("발사! 🚀");
    return;
  }

  console.log(n);
  countdown(n - 1);
}

countdown(3);

실행 과정:

1단계: countdown(3) 호출
  → 3 출력
  → countdown(2) 호출

2단계: countdown(2) 호출
  → 2 출력
  → countdown(1) 호출

3단계: countdown(1) 호출
  → 1 출력
  → countdown(0) 호출

4단계: countdown(0) 호출
  → "발사! 🚀" 출력
  → 종료

출력:
3
2
1
발사! 🚀

콜 스택 시각화:

countdown(3)이 호출되면 스택에 쌓입니다:

[countdown(0)] ← 기저 조건 도달, 여기서부터 풀림
[countdown(1)]
[countdown(2)]
[countdown(3)]
[main()]

각 함수는 자기 아래 함수가 끝날 때까지 기다립니다.

어떻게 동작하나요?

1. 팩토리얼(계승;factorial) - 가장 기본적인 예제

팩토리얼(Factorial)은 1부터 n까지의 모든 자연수를 곱한 값입니다. 수학적으로는 n!으로 표기합니다.

예를 들어, 5! = 5 × 4 × 3 × 2 × 1 = 120입니다.

재귀적 사고:

5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1 (기저 조건)

구현:

function factorial(n) {
  // 기저 조건: 1! = 1
  if (n <= 1) {
    return 1;
  }

  // 재귀 호출: n! = n × (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5));  // 120

실행 과정 시각화:

factorial(5)
= 5 × factorial(4)
= 5 × (4 × factorial(3))
= 5 × (4 × (3 × factorial(2)))
= 5 × (4 × (3 × (2 × factorial(1))))
= 5 × (4 × (3 × (2 × 1)))
= 5 × (4 × (3 × 2))
= 5 × (4 × 6)
= 5 × 24
= 120

2. 피보나치 수열

피보나치 수열(Fibonacci Sequence)은 첫 두 항이 0과 1이고, 그 다음 항부터는 앞의 두 항을 더한 값으로 이루어진 수열입니다.

0번째: 0
1번째: 1
2번째: 0 + 1 = 1
3번째: 1 + 1 = 2
4번째: 1 + 2 = 3
5번째: 2 + 3 = 5
6번째: 3 + 5 = 8
...

즉, F(n) = F(n-1) + F(n-2) 라는 규칙을 따릅니다.

function fibonacci(n) {
  // 기저 조건
  if (n <= 1) {
    return n;  // fib(0) = 0, fib(1) = 1
  }

  // 재귀 호출
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6));  // 8
// 0, 1, 1, 2, 3, 5, 8

호출 트리 시각화:

                    fib(6)
                   /      \
              fib(5)      fib(4)
              /    \      /    \
         fib(4)  fib(3) fib(3) fib(2)
         /   \   /   \   /  \   /   \
    fib(3) fib(2) ...

매우 많은 중복 계산이 발생합니다! (비효율적)

3. 배열의 합

// 반복문 버전
function sumLoop(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;
}

// 재귀 버전
function sumRecursive(arr) {
  // 기저 조건: 빈 배열
  if (arr.length === 0) {
    return 0;
  }

  // 재귀 호출: 첫 번째 요소 + 나머지의 합
  return arr[0] + sumRecursive(arr.slice(1));
}

console.log(sumRecursive([1, 2, 3, 4, 5]));  // 15

실행 과정:

sumRecursive([1, 2, 3, 4, 5])
= 1 + sumRecursive([2, 3, 4, 5])
= 1 + (2 + sumRecursive([3, 4, 5]))
= 1 + (2 + (3 + sumRecursive([4, 5])))
= 1 + (2 + (3 + (4 + sumRecursive([5]))))
= 1 + (2 + (3 + (4 + (5 + sumRecursive([])))))
= 1 + (2 + (3 + (4 + (5 + 0))))
= 15

재귀의 패턴

지금까지 팩토리얼, 피보나치, 배열의 합 같은 예제를 봤습니다. 그런데 자세히 보면 각각 재귀를 호출하는 방식이 다릅니다.

  • 팩토리얼: 자기 자신을 한 번만 호출
  • 피보나치: 자기 자신을 두 번 호출
  • 이진 탐색: 자기 자신을 한 번 호출하지만 범위를 절반으로 줄임

이런 패턴들을 이해하면, 새로운 문제를 만났을 때 “어떤 방식의 재귀를 써야 할까?”를 빠르게 판단할 수 있습니다.

패턴 1: 단순 재귀

하나의 재귀 호출만 하는 경우.

// 문자열 뒤집기
function reverse(str) {
  if (str === "") return "";
  return reverse(str.slice(1)) + str[0];
}

console.log(reverse("hello"));  // "olleh"

// 실행:
// reverse("hello")
// = reverse("ello") + "h"
// = (reverse("llo") + "e") + "h"
// = ((reverse("lo") + "l") + "e") + "h"
// = (((reverse("o") + "l") + "l") + "e") + "h"
// = ((((reverse("") + "o") + "l") + "l") + "e") + "h"
// = (((("" + "o") + "l") + "l") + "e") + "h"
// = "olleh"

패턴 2: 다중 재귀

여러 번 자기 자신을 호출하는 경우.

// 이진 트리 순회
function traverseTree(node) {
  if (node === null) return;

  console.log(node.value);      // 현재 노드 처리
  traverseTree(node.left);      // 왼쪽 서브트리
  traverseTree(node.right);     // 오른쪽 서브트리
}

// 트리 구조:
//       1
//      / \
//     2   3
//    / \
//   4   5

const tree = {
  value: 1,
  left: {
    value: 2,
    left: { value: 4, left: null, right: null },
    right: { value: 5, left: null, right: null }
  },
  right: { value: 3, left: null, right: null }
};

traverseTree(tree);
// 출력: 1, 2, 4, 5, 3

패턴 3: 분할 정복

문제를 절반씩 나누어 해결.

// 이진 탐색 (재귀 버전)
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  // 기저 조건: 범위를 다 찾음
  if (left > right) {
    return -1;
  }

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) {
    return mid;
  }

  // 절반씩 나누어 재귀
  if (arr[mid] < target) {
    return binarySearch(arr, target, mid + 1, right);  // 오른쪽 절반
  } else {
    return binarySearch(arr, target, left, mid - 1);   // 왼쪽 절반
  }
}

const arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(arr, 7));  // 3

재귀 vs 반복문

여기까지 읽으면서 “재귀가 이렇게 좋으면 왜 모든 곳에 쓰지 않을까?”라는 의문이 들 수 있습니다.

사실 대부분의 재귀 함수는 반복문으로도 작성할 수 있습니다. 그렇다면 언제 재귀를 쓰고, 언제 반복문을 써야 할까요?

각각의 장단점을 비교해보면서, 어떤 상황에서 어떤 방식이 더 적합한지 알아봅시다.

비교표

특징 재귀 반복문
가독성 간결하고 우아함 길고 복잡할 수 있음
성능 함수 호출 오버헤드 빠름
메모리 스택 메모리 사용 (위험) 적음
적합한 문제 트리, 그래프, 분할 정복 단순 반복
디버깅 어려움 쉬움

직접 비교: 거듭제곱 구현하기

표만 봐서는 실감이 안 날 수 있으니, 같은 문제를 두 가지 방식으로 구현해보겠습니다.

2의 5승을 계산하는 함수를 만들어볼까요? 반복문과 재귀, 어떤 차이가 있을까요?

// ✅ 반복문으로 거듭제곱
function powerLoop(base, exp) {
  let result = 1;
  for (let i = 0; i < exp; i++) {
    result *= base;
  }
  return result;
}

// ✅ 재귀로 거듭제곱
function powerRecursive(base, exp) {
  if (exp === 0) return 1;
  return base * powerRecursive(base, exp - 1);
}

console.log(powerLoop(2, 5));       // 32
console.log(powerRecursive(2, 5));  // 32

두 코드의 결과는 같지만, 작성 방식이 확연히 다릅니다:

  • 반복문: 변수(result, i)를 선언하고 for 루프로 명시적으로 반복합니다. 코드가 조금 더 길지만, 실행 과정을 단계별로 추적하기 쉽습니다.
  • 재귀: 기저 조건(exp === 0)만 정의하고, 나머지는 자기 자신을 호출합니다. 코드가 짧고 수학적 정의(power(base, exp) = base × power(base, exp-1))에 가깝습니다.

성능 면에서는 반복문이 더 빠르지만, 재귀가 문제의 본질을 더 명확하게 표현합니다.

언제 재귀를 사용할까요?

✅ 재귀가 좋은 경우:

  • 트리나 그래프 구조 탐색
  • 분할 정복 알고리즘
  • 백트래킹 문제
  • 코드의 간결함이 중요한 경우

❌ 재귀를 피해야 할 경우:

  • 단순 반복 작업
  • 성능이 매우 중요한 경우
  • 깊이가 매우 깊어질 수 있는 경우 (스택 오버플로우 위험)

함정과 주의사항

재귀는 강력하지만, 잘못 사용하면 프로그램이 멈추거나 매우 느려질 수 있습니다.

실제로 많은 개발자들이 재귀를 처음 사용할 때 같은 실수를 반복합니다. 이런 실수들을 미리 알고 있으면, 디버깅 시간을 크게 줄일 수 있습니다.

가장 흔한 4가지 함정을 살펴보고, 어떻게 피할 수 있는지 알아봅시다.

함정 1: 기저 조건이 없으면 무한 재귀

가장 치명적인 실수입니다. 재귀 함수에서 기저 조건(멈춤 조건)을 빼먹으면, 함수가 끝없이 자기 자신을 호출하다가 결국 스택 메모리가 꽉 차서 프로그램이 멈춥니다.

// ❌ 스택 오버플로우 발생!
function infiniteRecursion(n) {
  return infiniteRecursion(n - 1);  // 멈추지 않음!
}

// infiniteRecursion(5);  // Error: Maximum call stack size exceeded

// ✅ 올바른 구현
function properRecursion(n) {
  if (n <= 0) return;  // 기저 조건 필수!
  return properRecursion(n - 1);
}

함정 2: 피보나치의 성능 문제

같은 계산을 반복하면 성능이 급격히 나빠집니다. 앞에서 본 피보나치 재귀는 아름답지만, 실제로는 같은 값을 수백 번씩 다시 계산합니다. fib(40)을 호출하면 fib(5)가 수백만 번 호출되는 비효율이 발생합니다.

// ❌ 매우 느림 (지수 시간 복잡도)
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

console.time('느린 피보나치');
fibSlow(40);  // 몇 초 걸림
console.timeEnd('느린 피보나치');

// ✅ 메모이제이션으로 최적화
function fibFast(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];  // 이미 계산한 값 재사용

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

console.time('빠른 피보나치');
fibFast(40);  // 즉시 완료
console.timeEnd('빠른 피보나치');

// 느린 피보나치: 1000ms
// 빠른 피보나치: 0.5ms

함정 3: 꼬리 재귀 최적화

JavaScript의 꼬리 재귀 최적화는 믿을 수 없습니다. 일부 자료에서 꼬리 재귀(Tail Call Optimization)를 권장하지만, JavaScript는 엔진마다 지원 여부가 다릅니다. Safari만 지원하고 Chrome/Node.js는 지원하지 않으므로, 꼬리 재귀에 의존하면 브라우저에 따라 스택 오버플로우가 발생할 수 있습니다.

// ❌ 일반 재귀 (스택 쌓임)
function factorialNormal(n) {
  if (n <= 1) return 1;
  return n * factorialNormal(n - 1);  // 곱셈이 재귀 호출 후에 발생
}

// ✅ 꼬리 재귀 (일부 엔진에서 최적화)
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc);  // 마지막 동작이 재귀 호출
}

// 하지만 대부분의 경우 반복문이 더 안전합니다
function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

함정 4: 스택 오버플로우

재귀 깊이에는 한계가 있습니다. 재귀 호출이 너무 깊어지면 콜 스택이 꽉 차서 에러가 발생합니다. JavaScript는 브라우저마다 다르지만 보통 1만~2만 번 정도의 재귀 호출까지만 허용합니다. 깊이가 깊어질 수 있는 경우에는 반복문을 사용하는 것이 안전합니다.

// ❌ 깊이가 너무 깊으면 스택 오버플로우
function deepRecursion(n) {
  if (n <= 0) return;
  return deepRecursion(n - 1);
}

// deepRecursion(100000);  // Error!

// ✅ 반복문으로 해결
function deepLoop(n) {
  while (n > 0) {
    n--;
  }
}

deepLoop(100000);  // 문제 없음

실전 활용 예시

지금까지 팩토리얼이나 피보나치 같은 교육용 예제를 봤습니다. 하지만 “실무에서는 언제 재귀를 쓸까?”라는 의문이 들 수 있습니다.

실제로 재귀는 계층 구조를 다룰 때 가장 빛을 발합니다. 폴더 안의 폴더, 댓글의 대댓글, HTML 요소의 자식 요소처럼 깊이를 알 수 없는 중첩된 데이터를 다룰 때 재귀만큼 자연스러운 해결책은 없습니다.

5가지 실전 예시를 통해 재귀가 어떻게 복잡한 문제를 간단하게 해결하는지 살펴봅시다.

1. 폴더 구조 탐색

파일 시스템은 대표적인 트리 구조입니다. 폴더 안에 또 폴더가 있고, 그 안에 또 폴더가… 무한히 중첩될 수 있습니다. 반복문으로는 이런 구조를 탐색하기 어렵지만, 재귀로는 아주 간단합니다.

// 파일 시스템의 모든 파일 찾기
function findAllFiles(directory) {
  const files = [];

  function traverse(dir) {
    for (const item of dir.contents) {
      if (item.type === 'file') {
        files.push(item.name);
      } else if (item.type === 'directory') {
        traverse(item);  // 재귀적으로 하위 디렉토리 탐색
      }
    }
  }

  traverse(directory);
  return files;
}

const fileSystem = {
  type: 'directory',
  name: 'root',
  contents: [
    { type: 'file', name: 'index.html' },
    {
      type: 'directory',
      name: 'css',
      contents: [
        { type: 'file', name: 'style.css' },
        { type: 'file', name: 'reset.css' }
      ]
    },
    {
      type: 'directory',
      name: 'js',
      contents: [
        { type: 'file', name: 'app.js' }
      ]
    }
  ]
};

console.log(findAllFiles(fileSystem));
// ['index.html', 'style.css', 'reset.css', 'app.js']

2. DOM 트리 탐색

웹 페이지의 HTML 구조도 트리입니다. <div> 안에 <p>가 있고, 그 안에 <span>이 있고… 재귀로 모든 요소를 순회할 수 있습니다.

// 모든 HTML 요소의 텍스트 추출
function extractAllText(element) {
  let text = '';

  // 텍스트 노드인 경우
  if (element.nodeType === Node.TEXT_NODE) {
    return element.textContent;
  }

  // 요소 노드인 경우, 모든 자식 재귀 탐색
  for (const child of element.childNodes) {
    text += extractAllText(child);
  }

  return text;
}

// 사용 예:
const bodyText = extractAllText(document.body);

3. JSON 깊은 복사

객체 안에 객체가 중첩된 경우, ... 스프레드 연산자로는 얕은 복사만 됩니다. 재귀를 사용하면 아무리 깊은 구조라도 완전히 복사할 수 있습니다.

// 중첩된 객체/배열 깊은 복사
function deepClone(obj) {
  // 기저 조건: 원시 타입
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }

  // 배열인 경우
  if (Array.isArray(obj)) {
    return obj.map(item => deepClone(item));
  }

  // 객체인 경우
  const cloned = {};
  for (const key in obj) {
    cloned[key] = deepClone(obj[key]);  // 재귀적으로 복사
  }
  return cloned;
}

const original = {
  name: 'Alice',
  hobbies: ['reading', 'coding'],
  address: {
    city: 'Seoul',
    country: 'Korea'
  }
};

const copied = deepClone(original);
copied.address.city = 'Busan';

console.log(original.address.city);  // 'Seoul' (영향 없음)
console.log(copied.address.city);    // 'Busan'

4. 순열 생성

[1, 2, 3]의 모든 순열을 구하려면? 반복문으로는 중첩 깊이를 알 수 없어 어렵지만, 재귀로는 “첫 번째 원소를 고정하고 나머지의 순열을 구한다”는 간단한 논리로 해결됩니다.

// 배열의 모든 순열 생성
function permutations(arr) {
  // 기저 조건: 요소가 1개 이하
  if (arr.length <= 1) {
    return [arr];
  }

  const result = [];

  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
    const remainingPerms = permutations(remaining);

    for (const perm of remainingPerms) {
      result.push([current, ...perm]);
    }
  }

  return result;
}

console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

5. 미로 찾기 (백트래킹)

게임이나 퍼즐에서 미로의 출구를 찾는 문제는 재귀와 백트래킹의 전형적인 예시입니다. 4방향으로 계속 탐색하다가 막히면 돌아와서 다른 길을 시도하는 과정을 재귀로 자연스럽게 표현할 수 있습니다.

// 미로에서 출구 찾기
function solveMaze(maze, x, y, path = []) {
  // 기저 조건: 범위를 벗어남
  if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length) {
    return false;
  }

  // 기저 조건: 벽이거나 이미 방문함
  if (maze[x][y] === 1 || maze[x][y] === 'visited') {
    return false;
  }

  // 기저 조건: 출구 도달
  if (maze[x][y] === 'E') {
    path.push([x, y]);
    return true;
  }

  // 현재 위치 방문 표시
  maze[x][y] = 'visited';
  path.push([x, y]);

  // 4방향 탐색 (상하좌우)
  if (solveMaze(maze, x + 1, y, path) ||  // 아래
      solveMaze(maze, x - 1, y, path) ||  // 위
      solveMaze(maze, x, y + 1, path) ||  // 오른쪽
      solveMaze(maze, x, y - 1, path)) {  // 왼쪽
    return true;
  }

  // 백트래킹: 이 경로는 막힘
  path.pop();
  return false;
}

const maze = [
  [0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 0, 1, 'E']
];

const path = [];
solveMaze(maze, 0, 0, path);
console.log(path);  // 출구까지의 경로

재귀를 디버깅하는 방법

재귀 함수를 작성하다 보면 “어디서 잘못됐지?”, “왜 무한 루프가 도는 거지?”같은 상황을 자주 만나게 됩니다.

재귀는 함수 호출이 중첩되기 때문에 일반적인 디버깅 방법으로는 흐름을 파악하기 어렵습니다. 하지만 몇 가지 기법을 사용하면 재귀의 실행 과정을 눈으로 확인할 수 있습니다.

두 가지 실용적인 디버깅 기법을 알아봅시다.

1. 로그 추가

가장 효과적인 방법입니다. 각 재귀 호출의 깊이를 들여쓰기로 표시하면, 어떤 순서로 함수가 호출되고 반환되는지 시각적으로 확인할 수 있습니다.

function factorialDebug(n, depth = 0) {
  const indent = '  '.repeat(depth);
  console.log(`${indent}→ factorial(${n}) 호출`);

  if (n <= 1) {
    console.log(`${indent}← 기저 조건: 1 반환`);
    return 1;
  }

  const result = n * factorialDebug(n - 1, depth + 1);
  console.log(`${indent}← ${n} × factorial(${n-1}) = ${result}`);
  return result;
}

factorialDebug(4);

출력:

→ factorial(4) 호출
  → factorial(3) 호출
    → factorial(2) 호출
      → factorial(1) 호출
      ← 기저 조건: 1 반환
    ← 2 × factorial(1) = 2
  ← 3 × factorial(2) = 6
← 4 × factorial(3) = 24

2. 호출 횟수 추적

성능 문제를 발견하는 데 유용합니다. 재귀가 예상보다 느리다면, 함수가 몇 번이나 호출되는지 확인해보세요. 중복 계산이 많다면 메모이제이션을 고려해야 합니다.

let callCount = 0;

function fibWithCount(n) {
  callCount++;
  if (n <= 1) return n;
  return fibWithCount(n - 1) + fibWithCount(n - 2);
}

callCount = 0;
console.log(fibWithCount(10));  // 55
console.log(`총 호출 횟수: ${callCount}`);  // 177번!

연습 문제

1. 기본 - 배열의 최대값 찾기

// 재귀로 배열의 최대값 찾기
function findMax(arr) {
  // 힌트: 첫 번째 요소와 나머지의 최대값을 비교
}

console.log(findMax([3, 1, 4, 1, 5, 9]));  // 9

2. 중급 - 거듭제곱 (최적화)

// O(log n) 시간에 거듭제곱 계산
// 힌트: 2^8 = (2^4)^2, 2^9 = 2 × (2^4)^2
function fastPower(base, exp) {
  // 여기에 코드 작성
}

console.log(fastPower(2, 10));  // 1024

3. 고급 - 이진 트리의 높이

// 이진 트리의 최대 깊이 구하기
function maxDepth(node) {
  // 힌트: 1 + max(왼쪽 높이, 오른쪽 높이)
}

const tree = {
  value: 1,
  left: {
    value: 2,
    left: { value: 4, left: null, right: null },
    right: null
  },
  right: { value: 3, left: null, right: null }
};

console.log(maxDepth(tree));  // 3

참고 자료

공식 문서 및 표준

학술 자료 및 이론

  • Recursion - Wikipedia - 재귀의 역사와 이론
  • Tail Call Optimization - 꼬리 재귀 최적화
  • Introduction to Algorithms (CLRS) - Chapter 4: Divide-and-Conquer
  • Structure and Interpretation of Computer Programs (SICP) - Chapter 1.2: Procedures and Processes

시각화 및 학습 도구

실습 문제

관련 문서

심화 주제

마치며

재귀는 처음에는 어렵게 느껴지지만, “문제를 더 작게 만들어 해결한다”는 핵심만 이해하면 자연스러워집니다.

재귀는 많은 알고리즘의 기초입니다. 처음에는 어렵지만, 연습하면 트리나 그래프 문제를 훨씬 쉽게 풀 수 있게 됩니다! 💪

핵심은 두 가지입니다:

  1. 기저 조건 - 언제 멈출 것인가?
  2. 재귀 호출 - 문제를 어떻게 더 작게 만들 것인가?

학습 팁

  1. 직접 그려보세요: 호출 스택을 종이에 그려보면 이해가 쉽습니다
  2. 작은 값으로 테스트: n=3, n=4로 시작해서 패턴 파악
  3. 로그 찍어보기: console.log로 각 단계를 추적
  4. 반복문과 비교: 같은 문제를 두 가지 방식으로 풀어보기

다음 단계

같은 레벨 (초중급):

다음 레벨 (중급):

실전 응용:

🚀 추천 학습 순서: 재귀 → 메모이제이션 → DFS/BFS → 동적 프로그래밍

재귀를 마스터하는 3단계

  1. 기초 재귀 (팩토리얼, 피보나치) ← 지금 여기
  2. 트리/그래프 재귀 (DFS, 트리 순회)
  3. 백트래킹 (순열, 조합, 미로 찾기)

댓글