파이썬 알고리즘: 피보나치수열 구하기 || 재귀함수 호출

https://youtu.be/yhzs65QoGMc

 

1번: 가장 기본적인 방법 . 스왑 + For 루프 방식. 피보나치 수열의 F(0)과 F(1)은 미리 정의한다.

 

def fibonacci_loop(num): 
    if num <= 0: 
        print('F(',0,') : ',' ratio: 0',sep='') 
         
    elif num == 1: 
        print('F(',0,') : ',' ratio: 0',sep='') 
        print('F(',1,') : ',' ratio: 0',sep='') 
         
    elif num > 1: 
        a = 0 # first number 
        b = 1 # second 
        print('F(',a,') : ',a,' ratio: 0',sep='') 
        print('F(',b,') : ',b,' ratio: 0',sep='') 
        for i in range(2, num + 1): 
            c = a + b 
            a, b = b, c 
            print('F(',i,') : ',c ,' ratio: ',(b/a),sep='') 

        return c 


num = eval(input('enter a fibonacci number to calculate: ')) 
fibonacci_loop(num)

2번: 재귀함수호출

 

def fibonacci_recursion(num): 
    '''Return a fibonacci sequence value of num''' 
    if num == 0: 
        return 0 
    if num == 1 or num == 2: 
        return 1 

    return fibonacci_recursion(num - 2) + fibonacci_recursion(num - 1) 

a = fibonacci_recursion(int(input("enter a term :"))) 
print("number is :",a)

 

*실행속도가 매우 느리다.

 

3번 재귀함수 Cache: 2번보다 속도가 빠르다

 

cache = {} 

def fibonacci_cache(num): 
    '''Return a fibonacci sequence value of num''' 

    if num in cache: 
        return cache[num] 

    if num == 0: 
        result = 0 
    elif num == 1 or num == 2: 
        result = 1 
    else: 
        result = fibonacci_cache(num - 2) + fibonacci_cache(num - 1) 

    cache[num] = result 
    return result 


a=fibonacci_cache(int(input("number:"))) 
print(a) 
print(cache)

 

4번: LRU (LEAST RECENTLY USED) CACHE 사용

 

from functools import lru_cache 


@lru_cache(maxsize = 1000) 

def fibonacci(num): 
    '''Return a fibonacci sequence value of num''' 

    if num == 0: 
        return 0 
    if num == 1 or num == 2: 
        return 1 

    return fibonacci(num - 2) + fibonacci(num - 1) 


print(fibonacci(int(input("number:"))))