피보나치 수열 알고리즘

피보나치 수열

 

0과 1부터 시작해서 바로 앞의 두 수를 더한 값을 다음 값으로 추가하는 방식으로 만든 수열을 피보나치 수열이라고 한다.

즉, 0+1=1, 1+1=2, 1+2=3

0

1

1

2

3

5

8

13

a[0]

a[1]

a[0]+a[1]=1

a[1]+a[2]=2

a[2]+a[3]=3

a[3]+a[4]=5

a[4]+a[5]=8

a[5]+a[6]=13

 

• n번째 피보나치 수를 구하는 알고리즘을 재귀 호출을 이용해서 구현
• Python Language

def fibo(n):
    if n <= 1:
        return n
    return fibo(n-2) + fibo(n-1)
    
print(fibo(7)) # 13