4강: 재귀 알고리즘 기초

강의

"재귀함수"는 자신을 다시 호출하여 작업을 수행하는 알고리즘입니다.

예시로는 이진 트리와 자연수의 합 구하기가 있습니다.

 

재귀함수는 종결 조건을 작성하는 것이 매우 중요합니다.

 

모든 재귀함수는 반복문으로 작성이 가능합니다.

하지만 효율성이 항상 좋다고 할 수는 없습니다.

 

 

4강 실습: 피보나치 순열 구현하기

⭐ 직관적 풀이 : 반복문 이용하는 방법!

def solution(x):
    f = [0] * (x+1)
    print(f, x)
    
    if x == 0:
        return 0
    
    f[1] = 1
    
    for i in range(2, x+1):
        f[i] = f[i-2] + f[i-1]

    return f[-1]

⭐ 힌트 풀이 : 재귀함수 이용하는 방법!

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

def solution(x):
    ans = fibo(x)
    
    return ans