[어서와! 자료구조와 알고리즘은 처음이지?] 피보나치 수열 구하기

재귀 함수 이용해서 구하는 코드

def solution(x):
    answer = 0
    if x <= 1:
        return x
    else:
        answer = solution(x-1) + solution(x-2)
        return answer

 

 

반복문 이용해서 구하는 코드

def solution(x):
    fn_1 = 1 ##f1
    fn_2 = 0 ##f0
    fn = x
    while x>=2:
        fn = fn_1 + fn_2
        fn_2 = fn_1
        fn_1 = fn
        x -= 1
    return fn

 

반복문 버전은 프로그래머스의 다른 사람 코드를 참고 했다

 

 

재귀 알고리즘은 효율성이 떨어질 가능성이 크지만 생각을 직관적으로 표현이 가능하다는 장점이 있다