Recursion

Recursion (재귀)

재귀란 함수가 자기 자신을 호출하는 것이다. 구조는 단순하지만, 잘못 쓰면 엄청나게 비효율적인 코드가 되기도 한다. 이번 글은 복습하면서 헷갈렸던 부분을 중심으로 정리했다.

---

1. 재귀의 두 가지 구성 요소

재귀 함수는 반드시 두 가지를 가져야 한다.

• Base case: 재귀를 멈추는 조건
• Recursive call: 자기 자신을 호출해 base case로 다가가는 과정

여기서 base case를 "시작점"으로 생각하기 쉬운데, 정확히는 멈추는 조건이다. base case가 없으면 함수가 영원히 자기 자신을 호출하는 infinite recursion이 발생한다.

---

2. Factorial

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

재귀가 실제로 어떻게 동작하는지 보면 두 단계로 나뉜다.
 

내려가는 단계 (호출):

f(3) → 3 * f(2)
         → 2 * f(1)
              → 1 * f(0)
                   → 1  ← base case

 

올라오는 단계 (반환):

f(0) = 1
f(1) = 1 * 1 = 1
f(2) = 2 * 1 = 2
f(3) = 3 * 2 = 6

 

• Time complexity: O(n)

---

3. Binary Search

정렬된 배열에서 값을 찾는 알고리즘이다. 핵심 아이디어는 간단하다. 중앙값과 비교해서 찾는 값이 왼쪽에 있는지, 오른쪽에 있는지 판단하고, 탐색 범위를 절반씩 줄여나가는 것이다.

def binary_search(data, target, low, high):
    if low > high:
        return False
    else:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid - 1)
        else:
            return binary_search(data, target, mid + 1, high)

 
예를 들어 아래 배열에서 22를 찾는다고 하면:

[2, 4, 5, 7, 8, 9, 12, 14, 17, 19, 22, 25, 27, 28, 33, 37]
  0  1  2  3  4  5   6   7   8   9  10  11  12  13  14  15

단계	low	high	mid	data[mid]	방향
1	0	15	7	14	오른쪽
2	8	15	11	25	왼쪽
3	8	10	9	19	오른쪽
4	10	10	10	22	찾음!

매 단계마다 탐색 범위가 절반씩 줄어드니, 이는 밑이 2인 로그 함수와 같다. n = 10억이어도 딱 30번이면 충분하다.
 

• Time complexity: O(log n)

---

4. Tower of Hanoi

n개의 디스크를 rod 1에서 rod 2로 옮기는 문제다. 규칙은 한 번에 하나씩만, 그리고 큰 디스크 위에 작은 디스크만 올릴 수 있다.

재귀적으로 생각하면 이렇다.

1. n-1개의 디스크를 rod 1 → rod 3으로 옮긴다
2. 가장 큰 디스크를 rod 1 → rod 2로 옮긴다
3. n-1개의 디스크를 rod 3 → rod 2로 옮긴다

Base case는 n = 1일 때, 즉 디스크가 1개일 때 그냥 바로 옮기면 된다.

def Hanoi(n, loc_from, loc_to):
    if n <= 0:
        return
    loc_aux = 6 - loc_from - loc_to
    Hanoi(n-1, loc_from, loc_aux)
    print("Move a disk from rod " + str(loc_from) + " to rod " + str(loc_to))
    Hanoi(n-1, loc_aux, loc_to)

 
총 이동 횟수 T(n)을 구해보면:

T(1) = 1
T(2) = 2*1 + 1 = 3
T(3) = 2*3 + 1 = 7
T(4) = 2*7 + 1 = 15

패턴을 보면 2ⁿ - 1이다.

• Time complexity: O(2ⁿ)

---

5. Bad Recursion vs Good Recursion: Fibonacci

bad_fibonacci

def bad_fibonacci(n):
    if n <= 1:
        return n
    else:
        return bad_fibonacci(n-2) + bad_fibonacci(n-1)

수학적 정의를 그대로 옮긴 코드인데, 실제로는 매우 비효율적이다. 이유는 중복 계산 때문이다.
 
bad_fibonacci(4)를 호출하면 내부적으로 이렇게 펼쳐진다.

bad_fibonacci(4)
├── bad_fibonacci(3)
│   ├── bad_fibonacci(2)
│   │   ├── bad_fibonacci(1)
│   │   └── bad_fibonacci(0)
│   └── bad_fibonacci(1)   ← 이미 계산했는데 또!
└── bad_fibonacci(2)       ← 이미 계산했는데 또!
    ├── bad_fibonacci(1)
    └── bad_fibonacci(0)

n이 커질수록 이 중복이 기하급수적으로 쌓인다.

• Time complexity: O(2ⁿ)

good_fibonacci

비효율성의 원인은 f(n-1)을 계산할 때 f(n-2)를 다시 계산한다는 것이다. 이미 알고 있는 값을 재활용하면 어떨까?

해결 방법은 함수가 두 개의 값을 동시에 반환하게 만드는 것이다. good_fibonacci(n)은 (F(n), F(n-1))을 한 쌍으로 반환한다.

def good_fibonacci(n):
    if n <= 1:
        return (n, 0)
    else:
        (a, b) = good_fibonacci(n-1)
        return (a+b, a)

 
실제로 어떻게 동작하는지 보면:

good_fibonacci(1) = (1, 0)   → (F(1), F(0))
good_fibonacci(2) = (1, 1)   → (F(2), F(1))
good_fibonacci(3) = (2, 1)   → (F(3), F(2))
good_fibonacci(4) = (3, 2)   → (F(4), F(3))

재귀 호출이 매번 딱 한 번만 일어난다. F(n-2)를 다시 계산할 필요 없이 이미 반환된 b에서 꺼내 쓸 수 있기 때문이다.
 

• Time complexity: O(n)

---

6. Good Recursion: Power Function

power(x, n) = xⁿ을 재귀로 구현할 때도 두 가지 방법이 있다.
 

단순한 버전 (O(n))

def power(x, n):
    if n == 0:
        return 1
    else:
        return x * power(x, n-1)

n을 1씩 줄여나가니 O(n)이다.
 

빠른 버전 (O(log n))

핵심 아이디어는 squaring이다. 예를 들어 2¹²를 구하려면 2⁶을 구한 다음 제곱하면 된다. n을 절반씩 줄여나갈 수 있다.

def power(x, n):
    if n == 0:
        return 1
    else:
        partial = power(x, n // 2)
        result = partial * partial
        if n % 2 == 1:
            result *= x
        return result

power(2, 13)의 흐름을 보면:

power(2, 13)
└── power(2, 6)
    └── power(2, 3)
        └── power(2, 1)
            └── power(2, 0) = 1

n이 매번 절반씩 줄어드니 Binary Search와 같은 원리로 O(log n)이 된다.

---

7. Time Complexity 정리

알고리즘	Time Complexity
Factorial	O(n)
Binary Search	O(log n)
Tower of Hanoi	O(2ⁿ)
bad_fibonacci	O(2ⁿ)
good_fibonacci	O(n)
linear_sum	O(n)
bad power	O(n)
good power	O(log n)

패턴을 보면 이렇게 정리된다.

• 매번 1씩 줄어들면 → O(n)
• 매번 절반씩 줄어들면 → O(log n)
• 매번 2배씩 늘어나면 → O(2ⁿ)