(파이썬) 피보나치 수열의 재귀적 구현

피보나치 수열은 흔히 재귀적으로 정의하는 또 따른 수학적인 함수이다.

예를 들어 새로 태어난 두 마리 토끼가 우리 안에 있다고 가정해본다. 한마리는 수컷이고 한 마리는 암컷이다. 이 토끼들은 출생한지 한 달이 지나면 가능하며 임신 기간은 한 달이라고 해본다.

만약 이런 특성을 가진 토끼들이 절대로 죽지 않으며 암토끼가 출산할 때마다 수컷과 암컷 토끼를 한마리씩 낳는다고 하면 6개월 후 임신한 토끼는 몇마리나 될까?

개월	암토끼
0	1
1	1
2	2
3	3
4	5
5	8

6개월 후 임신한 토끼 마리 수

6

13

위의 테이블에서 개월 수가 1보다 큰 경우의 식은 다음과 같다.

females(n) = females(n-1) + females(n-2)

각 암토끼는 n-1개월 동안 살아있으며 n개월에도 살아있을 것이다. 거기에다 각 n-2개월에 살아있던 각 암토끼는 n개월에 새로운 암토끼를 출생할 것이다. 그러므로 새로 출생한 암토끼의 수를 n-1개월에 살아있는 암토끼의 수에 더하여 n개월에 살아있는 암토끼의 수를 구하게 된다.

개체수의 증가는 반복을 통해 나타난다.

females(0) = 1 females(1) = 1 females(n + 2) = females(n+1) + females(n)

이것은 피보나치 반복과 그것을 테스트할 수 있는 테스트 함수를 함께 구현한 것이다.

# 피나보치 수열의 재귀적 구현
def fib(n):
    """Assume n an int >= 0
       Returns Fibonacci of n"""
    if n == 0 or n ==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
def testFib(n):
    for i in range(n+1):
        print('fib of', i, '=', fib(i))

print('n개월 후 수량 : ', fib(6))
print('testFib : ', testFib(6))

출력결과 

n개월 후 토끼 마리 수 :  13
fib of 0 = 1
fib of 1 = 1
fib of 2 = 2
fib of 3 = 3
fib of 4 = 5
fib of 5 = 8
fib of 6 = 13
testFib :  None