4. 재귀 알고리즘 응용

재귀 알고리즘 (recursive algorithms) - 응용

• 조합의 수 (n 개의 서로 다른 원소에 m 개를 택하는 경우의 수) 구하기
• 하노이의 탑 (크기 순서로 쌓여 있는 원반을 한 막대에서 다른 막대로 옮기기)
• 피보나치 순열

조합의 수

n 개의 서로 다른 원소에 m 개를 택하는 경우의 수

# 빠른 풀이
from math import factorial as f


def combi(n,m):
    return f(n) / (f(m) * f(n-m))

조합의 수 계산 - 재귀적 방법

특정한 하나의 원소 입장에서 볼 때, 이 해당 원소를 포함하는 경우와 그렇지 않은 경우를 따로 계산해서 더한다.

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

하노이의 탑 (재귀 알고리즘의 유용성)

피보나치 순열

def rec_fivo(n): # 재귀적
    if n <= 1:
        return 1:
    else:
        return fibo(n-1) + fibo(n-2)

def iter_fivo(n): # 반복적
    if n <= 1
        return n
    else:
        i = 2
        t0 = 0
        t1 = 1
        while i <= n:
            t0, t1 = t1, t0 + t1
            i += 1
        return t1

위 두 함수는 수가 커질수록 효율성에서 많은 차이가 난다. 이처럼 재귀적 함수를 만들어 사용할 땐 효율성 측면을 고려해야한다.

# 연습문제 - 재귀적 이진 탐색

def solution(L, x, l, u):
    if x < L[l] or x > 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)

처음엔 탈출 조건으로 if not x in L: 을 하였는데 재귀 할때마다 선형적으로 탐색하여 L의 크기가 커질 수록 효율성이 떨어진다고 생각하였고 조건을 변경하였다.