자료구조와 알고리즘5

재귀 알고리즘 (Recursive Algorithms) 응용

5.재귀 알고리즘 응용

재귀 알고리즘 응용의 예 - 조합의 수 계산
n개의 서로 다른 원소에서 m개를 택하는 경우의 수

$\begin{pmatrix}n\\m\\ \end{pmatrix}$ = $\frac{1+s}{s(s+2)}$

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

재귀적인 방법

$\begin{pmatrix}n\\m\\ \end{pmatrix}$ = $\begin{pmatrix}n-1\\m\\ \end{pmatrix}$ + $\begin{pmatrix}n-1\\m-1\\ \end{pmatrix}$

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)

재귀적인 방법의 경우엔 실행과정에서 계속 함수를 호출하기에 반복적인 방법보다 실행 시간이 오래걸린다

대신 직관적인 알고리즘을 만들 수 있다

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)