5강: 재귀 알고리즘 응용

---

재귀함수(Recursive Functions)

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

예제

조합의 수 계산

• 문제 : n개의 서로 다른 원소에서 m개를 선택하는 경우의 수를 계산

• 코드 (iterative version)

from math import factorial as f

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

• 코드 (recursive version)

def combi(n,m):
	if n == m:
    	return 1
    if 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)

---

실습

재귀적 이진탐색 구현하기

코드

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)

---