[Python][알고리즘] 재귀 알고리즘 - 기초

 

 

 

 - Recursive version

def sum(n):
    if n <= 1:
        return n
    else:
        return n + sum(n-1)

복잡도 : O(n)

n 이 1 이하인 경우에 대해 다루는 부분 작성을 잊지말자

 ( = Trivial Case )

 

 

 

 

 - Iterative version

def sum(n):
    s = 0
    while n >= 0
        s += n
        n -= 1
    return s

복잡도 : O(n)

 

 

 

 

Recursive 버전과 Iterative 버전의 복잡도는 모두 O(n)으로 같지만, 함수를 호출하는 부분이 있는 Recursive 버전이 효율적으로는 뒤쳐집니다.

 

 

 

 

 - 수학적인 부분 활용

def sum(n):
    return n*(n+1)/2

 

 

 

 

 - 피보나치 수열

def fibonacci(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return fibonacci(x-1) + fibonacci(x-2)