재귀(Recursion)

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 함수의 재귀적 호출의 이해

• 재귀함수: 함수 내에서 자기 자신을 다시 호출하는 함수
• 실제로는 재귀함수가 실행되는 경우, 원본의 복사본이 하나 더 만들어져 복사본을 실행하게 됨

 

2. 재귀의 활용

피보나치 수열

$$ fib(n) = \begin{cases} 0, & \text{if } n = 1 \\ 1, & \text{if } n = 2 \\ fib(n-1) + fib(n-2), & \text{otherwise } \end{cases} $$

• fib(n) 실행 시, fib(n-1)가 다시 호출되고 이후, fib(n-2)가 실행됨

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

console.log(fibonacci(10));  // 결과: 55

3. 하노이 타워

• 기둥이 3개가 있고 맨 왼쪽 기둥에 있는 원반을 맨 오른쪽으로 그대로 옮기는 게임
• 큰 원반이 작은 원반 위에 있으면 안됨
• 원반의 개수가 n으로 무한히 커져도 변하지 않는 과정이 있음

1. 작은 원반 n-1개를 기둥 A에서 B로 이동
2. 큰 원반 1개를 A에서 C로 이동
3. 작은 원반 n-1개를 B에서 C로 이동

→ from에 꽃혀있는 num개의 원반을 by를 거쳐 to로 이동

※ 탈출 조건: 이동해야 할 원반의 개수가 1개인 경우

function hanoi(n, start, end, aux) {
  if (n === 1) {
    // 원반이 하나일 경우 직접 목표 지점으로 이동
    console.log(`Move disk 1 from ${start} to ${end}`);
    return;
  }

  // n-1개의 원반을 보조 기둥으로 이동
  hanoi(n - 1, start, aux, end);

  // 가장 큰 원반을 목표 기둥으로 이동
  console.log(`Move disk ${n} from ${start} to ${end}`);

  // n-1개의 원반을 목표 기둥으로 이동
  hanoi(n - 1, aux, end, start);
}

// 예시: 원반 3개를 A에서 C로 이동
hanoi(3, 'A', 'C', 'B');

• 출력 결과

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

 

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)