5강: 재귀 알고리즘 응용

강의

재귀 알고리즘을 응용할 수 있는 실제 예시를 풀어보았습니다.

1) 조합 : 같은 방법으로 순열이나 팩토리얼 계산도 가능할 것이라고 생각합니다.

2) 하노이의 탑

3) 피보나치 순열 : 재귀적 이진탐색으로 효율성을 높일 수 있습니다. 그러나 f(n)을 구하기 위해 f(n-10)을 여러번 계산해야 하는 부분에서 더욱 좋은 코드를 작성할 수 있을 것이라고 예상합니다.

 

 

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)