04. 피보나치 순열 (반복적 방식, 재귀적 방식)

<문제>

인자로 0 또는 양의 정수인 x 가 주어질 때, Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.

Fibonacci 순열은 아래와 같이 정의됩니다.
F0 = 0
F1 = 1
Fn = Fn - 1 + Fn - 2, n >= 2

재귀함수 작성 연습을 의도한 것이므로, 재귀적 방법으로도 프로그래밍해 보고, 반복적 방법으로도 프로그래밍해 보시기 바랍니다.

 

 

1. 반복적 방식

def solution(x):

    f=[]

    f0=0

    f1=1

    f.append(f0)

    f.append(f1)

    for i in range(x):

        f.append(f[i]+f[i+1])

    return f[x] 

#0 1 1 2 3 5 8 13 21

-테스트 결과

직접 피보나치 순열을 만들어 해당 값을 출력하게 만들었다.

 

2. 재귀적방식

def solution(x):

    if 0<x<=2:

        return 1

    elif x==0:

        return 0

    

    return solution(x-1)+solution(x-2)

#0 1 1 2 3 5 8 13 21

난 왜 재귀적 알고리즘이 더 오래걸릴까...

 

그리고 마음에 드는 풀이 캡쳐