피보나치 수열(반복문, 재귀함수)

 

피보나치 수열이란?

1부터 시작하여 1,2 인덱스를 더하면 3인덱스의 답이되고, 2,3인덱스를 더하면 4 인덱스의 답이 되는 수열이다..

1, 1, 2, 3, 5, 8 ........

 

반복문을 이용하는 방법과 재귀 함수를 이용하는 두 가지 방법이 있다.

먼저 반복문을 이용하는 방법이다

# 반복문을 이용하는 방법
def fibonacci_for(n):
    list = []
    if n<=0:
        return []
    elif n == 1:
        return [1]
    elif n == 2:
        return [1, 1]
    
    sequence = [1, 1]
    for i in range(2, n):
        sequence.append(sequence[i-1] + sequence[i-2])
    return sequence

 

print(fibonacci_for(n)) 을 이용해

숫자 n을 입력하면 n째 자리까지의 피보나치 수열이 출력된다!

 

0,1,2가 들어오면 더하기 수식이 필요없으니 if문으로 경우의 수를 제거해주고

첫 두 수 1과 1을 리스트로 저장해 그 다음 수부터 for문을 이용하는 방법이다.

앞의 두 인덱스가 이미 저장되었기 때문에 그 뒤 인덱스인 2부터 반복을 시작한다.

 

n=3이라면,

i = 2부터 시작해서 sequence[1]+sequence[0]=2

i = 3에는 sequence[2]+sequence[1]=3

이렇게 반복된다.

 

재귀함수를 이용하면 아래 코드가 조금 달라진다.

# 재귀를 이용한 방법
def fibonacci(n):
    if n<=0:
        return []
    elif n==1:
        return [1]
    elif n==2:
        return [1,1]
    else:
        list = fibonacci(n-1)
        list.append(list[-1]+ list[-2])
        return list

 

결과는 위 코드와 똑같다.

 

n이 0, 1, 2일때는 같고,

n>=3일때부터 재귀가 시작된다.

list에 fibonacci(n-1)을 대입하며 재귀를 시작해 첫 리턴인 n=2일때의 리턴값을 먼저 받아온다.

리턴을 받은 list는 마이너스 인덱스를 이용해 뒤에서부터 2개의 값을 더해 리스트에 append한다.

 

피보나치 수열은 유명한 알고리즘이니 외워두는 게 좋겠다...