재귀 (Recursion)

거울 앞에 거울을 놓으면 무한히 반복되는 모습을 볼 수 있다. 이처럼 자기 자신을 참조하는 것을 재귀라고 한다. 

프로그래밍에서 재귀는 함수가 자기 자신을 호출하는 것을 의미한다.

 

재귀 (Recursion)

재귀는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 프로그래밍에서는 함수가 자기 자신을 호출하는 재귀 함수로 구현된다.

재귀 함수의 필수 요소

재귀 함수는 탈출 조건(기저 조건)이 없으면 무한히 자신을 호출하기 때문에, 결국 스택 메모리가 가득 차서 프로그램이 종료된다.(Stack Overflow).

 

따라서 재귀 함수에는 반드시 다음 두 가지가 필요하다.

	설명
기저 조건 (Base Case)	재귀를 멈추는 조건
재귀 호출 (Recursive Call)	자기 자신을 호출하는 부분

 

간단한 재귀 함수 예시

1부터 10까지 출력하기

function myFunction(number) {
  if (number > 10) return;  // 기저 조건: 10을 넘으면 멈춤
  console.log(number);
  myFunction(number + 1);   // 재귀 호출
}

myFunction(1);  // 1부터 10까지 출력

이 함수는 다음과 같이 동작한다:

1. myFunction(1) 호출 → 1 출력 → myFunction(2) 호출
2. myFunction(2) 호출 → 2 출력 → myFunction(3) 호출
3. ...
4. myFunction(10) 호출 → 10 출력 → myFunction(11) 호출
5. myFunction(11) 호출 → number > 10 이므로 종료

 

팩토리얼 (Factorial)

팩토리얼은 재귀의 대표적인 예시다.

5! = 5 x 4 x 3 x 2 x 1 = 120

function factorial(number) {
  if (number == 1 || number == 0) {
    return 1;  // 기저 조건: 0! = 1, 1! = 1
  } else {
    return number * factorial(number - 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

 

재귀적으로 생각하기

재귀 함수는 크게 두 가지 패턴으로 나눌 수 있다.

패턴 1: 단순 반복 실행

다음은 for문을 재귀로 바꾼 형태이다.

// for문
for (let i = 1; i < 11; i++) {
  console.log(i);
}

// 재귀
function myFunction(number) {
  if (number > 10) return;
  console.log(number);
  myFunction(number + 1);
}
myFunction(1);

이 패턴은 콜스택에 공간을 많이 차지해 for문보다 성능이 안 좋다. 따라서 단순 반복은 for문을 사용하는 것이 좋다.

 

패턴 2: 하향식 계산

하위 문제의 결과를 기반으로 현재의 문제를 계산하는 패턴이다.

상향식 계산은 for문이나 재귀함수로 구현할 수 있지만, 하향식 계산은 오직 재귀함수로만 구현할 수 있다.

 

상향식 계산(for문)은 작은 값부터 차례대로 계산해 나간다.

function factorial(number) {
  let sum = 1;
  for (let i = 1; i <= number; i++) {
    sum *= i;  // 1 * 2 * 3 * 4 * 5
  }
  return sum;
}

 

하향식 계산(재귀)은 큰 문제를 작은 문제로 나누어 해결한다.

function factorial(number) {
  if (number == 1 || number == 0) {
    return 1;
  } else {
    return number * factorial(number - 1);  // 5! = 5 * 4!
  }
}

 

재귀함수의 진정한 위력은 하향식 계산에서 발휘된다고 할 수 있다.

 

하향식 재귀 함수 예시

1. 배열의 합

function sumArray(arr) {
  if (arr.length == 1) return arr[0];  // 기저 조건: 요소가 1개면 그 값을 반환
  return sumArray(arr.slice(0, -1)) + arr[arr.length - 1];
}

let arr = [1, 2, 3, 4, 5];
console.log(sumArray(arr));  // 15

동작 과정은 다음과 같다

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

 

2. 하노이의 탑

하노이의 탑은 재귀의 고전적인 예제이다.

 

규칙:

1. 한 번에 하나의 원반을 움직일 수 있다.
2. 가장 위에 있는 원반만 옮길 수 있다.
3. 아래에 작은 원반이 올수 없다.

function hanoi(count, from, to, temp) {
  if (count == 0) return;  // 기저 조건
  
  // 1. n-1개를 시작점에서 임시 기둥으로 이동
  hanoi(count - 1, from, temp, to);
  
  // 2. 가장 큰 원반을 시작점에서 목표점으로 이동
  console.log(`원반 ${count}이 ${from}에서 ${to}로 이동`);
  
  // 3. n-1개를 임시 기둥에서 목표점으로 이동
  hanoi(count - 1, temp, to, from);
}

hanoi(3, "A", "C", "B");
// 출력 결과
// 원반 1이 A에서 C로 이동
// 원반 2이 A에서 B로 이동
// 원반 1이 C에서 B로 이동
// 원반 3이 A에서 C로 이동
// 원반 1이 B에서 A로 이동
// 원반 2이 B에서 C로 이동
// 원반 1이 A에서 C로 이동

 

3개의 원반을 옮기려면 7번의 이동이 필요하다. 즉, n개의 원반을 옮기려면 2^n - 1번의 이동이 필요하다.

 

재귀의 장단점

장점

• 코드가 간결하고 이해하기 쉽다: 복잡한 문제를 단순하게 표현할 수 있다.
• 하향식 사고가 가능하다: 큰 문제를 작은 문제로 분할하여 해결할 수 있다.

단점

• 성능 저하: 함수 호출마다 스택 메모리를 사용하므로 반복문보다 느리다.
• 스택 오버플로우: 재귀 깊이가 너무 깊으면 스택 메모리가 부족해진다.
• 디버깅 어려움: 호출 스택이 복잡해져 디버깅이 어려울 수 있다.

 

재귀를 사용해야 할 때

다음과 같은 경우에 재귀를 사용하는 것이 좋다.

1. 트리 구조 탐색: 파일 시스템, DOM 트리 등
2. 분할 정복 알고리즘: 병합 정렬, 퀵 정렬 등
3. 조합/순열 생성: 모든 경우의 수를 구할 때
4. 백트래킹: N-Queen 문제, 미로 찾기 등

반면, 단순 반복이나 성능이 중요한 경우에는 for문이나 while문을 사용하는 것이 좋다.

 

재귀는 자기 자신을 호출하는 강력한 프로그래밍 기법이다. 복잡한 문제를 작은 문제로 분할하여 해결할 수 있으며, 특히 트리 구조나 분할 정복 알고리즘에서 빛을 발한다. 하지만 성능 문제와 스택 오버플로우 위험이 있으므로, 적재적소에 사용하는 것이 중요하다.