[자료구조&알고리즘] 재귀 알고리즘(2)

※ 재귀 알고리즘(recursive algorithm)

- 다음 예시들은 재귀 알고리즘을 활용하여 풀이를 할 수 있다.

• 조합의 수 (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 1
    else:
		return combi(n-1, m) + combi(n-1, m-1)

• 하노이의 탑(크기 순서로 쌓여 있는 원반을 한 막대에서 다른 막대로 옮기기
• 피보나치 수열

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