[Programmers-python algorithm] - 5강

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

문제의 종류에 따라 재귀 알고리즘을 적용하여 알고리즘을 간단하고 이해하기 쉽게 서술할 수 있다는 장점이 있다.
하지만 일반적으로 주어진 문제에 대해서 반복적인 알고리즘이 제귀적인 알고리즘보다 시작적 효율이 더 높다.
그럼에도 불구하고 사람의 생각을 코드로 옮겨놓을 수 있다는 특성 때문에 tree와 같은 자료구조를 이용하는 알고리즘에는 매우 직관적으로 적용할 수 있는 경우가 많다.

재귀알고리즘을 이용하여 다음의 문제들을 풀 수 있다.

(1) 조합의 수 (n 개의 서로 다른 원소애서 m개를 택하는 경우의 수) 구하기

// Trivial case를 고려해야 한다.
// n=m 일 때와 m=0일 때 이외에 재귀를 사용하여 구현한다.
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)

(2) 하노이의 탑 (크기 순서로 쌓여 있는 원반을 한 막대에서 다른 막대로 옮기기)
하노이의 탑은 추후 올릴 예정....

(3) 피보나치 수열

from math import factorial as f
def combi(n,m):
    return f(n)/f(m)*f(n-m)

재귀함수의 효율성과 관련하여 위의 피보나치 수열을 예로 들어보자.
fibo(4) = fibo(3)+fibo(2) fibo(4)를 계산하기 위해 아래의 연산들을 진행하게 된다.

• fibo(3) = fibo(2) + fibo(1)
  • fibo(2) = fibo(1) + fibo(0)
• fibo(2) = fibo(1) + fibo(0)
  총 9번의 함수를 호출한다.

(4) Binary Search
[Programmers-python algorithm] - 3강 에 포스팅 했던 Binary Search도
재귀적인 방법으로 구현이 가능하다.
아래의 링크를 통해 확인이 가능하다.
5-binsrrch.py