재귀 알고리즘(Recursive Algorithm)

재귀함수(recursive function)란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것

 

📌 간단한 예 - 자연수의 합 구하기

문제: 1부터 n 까지 모든 자연수의 합을 구하라.

$S = \sum_{k=1}^n  = n + \sum_{k=1}^{n-1} k$

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

📌 재귀 함수의 경우 종결 조건이 매우 중요하다 -> 안그러면 무한 루프에 빠짐

---

4강 실습: 피보나치 순열 구현하기

$F0 = 0$

$F1 = 1$

$F_n = F_{n-1} + F_{n-2}$

# 재귀적
def solution(x):
    answer = 0
    if x  == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return solution(x-1) + solution(x-2)
        

# 반복문
def solution(x):
    a, b = 1, 1
    if x == 1 or x == 2:
        return 1
    for _ in range(1, x):
        a, b = b, a+b
    return a

---

• 조합의 수 계산
  • 문제: n개의 서로 다른 원소에서 m개를 택하는 경우의 수
  • $\left(\begin{array}{c}n\\ m\end{array}\right) = \frac{n!}{m!(n-m)!}$
  • 이 문제의 점화식은 다음과 같음
  • $\left(\begin{array}{c}n-1\\ m\end{array}\right) + \left(\begin{array}{c}n-1\\ m-1\end{array}\right)$
  • m번째를 택해야 하는 경우일때 특정 원소가 들어갈 경우와 들어가지 않을 경우를 고려해주면 됨.
  • 즉 이전단계에서까지 선택을 안했다가 이번에 선택을 한 경우, 그리고 이전단계에서 선택했던 경우를 포함해서 더해주면 됨.

def combi(n, m):
    if n == m:
        return 1
    elif m == 0:
        return 1
    else:
        return combi(n-1, m) + combi(n-1, m-1)

• 하노이 탑

# n: 옮기려는 원판수
# from_pos: 어디서 출발하는지
# to_pos: 어디로 갈건지
# aux_pos: 중간에 잠시 들르는 기둥
def hanoi(n, from_pos, to_pos, aux_pos):
    if n == 1:
        print(from_pos, '->', to_pos)
        return
    hanoi(n - 1, from_pos, aux_pos, to_pos)
    print(from_pos, '->', to_pos)
    hanoi(n - 1, aux_pos, to_pos, from_pos)

hanoi(3, 1, 3, 2)

# 1 -> 3
# 1 -> 2
# 3 -> 2
# 1 -> 3
# 2 -> 1
# 2 -> 3
# 1 -> 3

---

5강 실습: 재귀적 이진 탐색 구현하기

def solution(L, x, l, u):
    if l > u:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l, mid-1)
    else:
        return solution(L, x, mid+1, u)