파이썬으로 피보나치 수열 코딩하는 방법: 반복문과 재귀 완벽 가이드

피보나치 수열은 수학에서 가장 유명한 수열 중 하나입니다. 계산 방법도 매우 간단합니다. 수열의 각 숫자는 바로 앞에 있는 두 숫자의 합입니다.

이 수열은 프로그래밍 분야에서도 널리 활용됩니다. 특히 알고리즘과 반복문을 학습하는 개발자 교육 과정에서 자주 등장하는 대표적인 예제입니다.

이 가이드에서는 파이썬으로 피보나치 수열을 구현하는 방법을 알아보겠습니다. 반복(iterative) 방식과 재귀(recursive) 방식, 두 가지 접근법을 코드 예제와 함께 살펴봅니다.

피보나치 수열이란?

피보나치 수열은 일련의 숫자로 이루어진 수열입니다. 각 숫자는 수열에서 자신의 앞에 있는 두 숫자의 합으로 계산됩니다. 수열은 다음과 같이 시작합니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

새로운 숫자를 계산하는 것을 멈출 때까지 이 수열은 무한히 이어집니다. 다음 숫자를 계산하는 규칙은 다음과 같습니다.

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

여기서 x(n)은 수열의 다음 숫자, x(n-1)은 바로 앞의 항, x(n-2)는 그 앞의 항을 의미합니다.

파이썬 피보나치 수열: 반복(Iterative) 접근 방식

먼저 반복문을 사용해 피보나치 수열을 구현하는 방법부터 살펴보겠습니다.

이 방식은 while 루프를 사용하여 특정 조건이 충족될 때까지 목록의 다음 숫자를 계산합니다. while 루프가 실행될 때마다 코드가 한 번씩 반복되기 때문에 이 접근법을 '반복적(iterative)'이라고 부릅니다.

먼저 몇 가지 초기값을 설정하겠습니다.

terms_to_calculate = 9
n1, n2 = 0, 1
counted = 0

세 개의 변수를 선언했습니다.

첫 번째 변수는 계산하고자 하는 값의 개수를 추적합니다. 다음 두 변수인 n1과 n2는 목록의 첫 두 항목입니다. 프로그램이 어디서부터 시작해야 할지 모르기 때문에 이 값들을 반드시 지정해야 합니다. 새로운 숫자를 계산하기 시작하면 이 값들은 계속 변경됩니다.

마지막 변수는 파이썬 프로그램에서 지금까지 계산한 항의 개수를 추적합니다.

이제 피보나치 수를 계산하는 루프를 작성해 보겠습니다.

while counted < terms_to_calculate:
    print(n1)
    new_number = n1 + n2
    n1 = n2
    n2 = new_number
    counted += 1

이 while 루프는 계산한 값의 개수가 원하는 총 개수와 같아질 때까지 실행됩니다. 루프는 n1의 값을 셸에 출력한 다음, 수열에서 바로 앞의 숫자와 그 앞의 숫자를 더해 다음 숫자를 계산합니다.

그다음 n1의 값을 n2와 같게 만듭니다. 이렇게 하면 n1이 새 숫자 바로 뒤에 오는 첫 번째 숫자가 됩니다. 이어서 n2를 새로운 숫자로 설정하고, += 연산자를 사용해 counted 변수에 1을 더합니다.

코드를 실행하면 다음과 같은 결과가 출력됩니다.

0
1
1
2
3
5
8
13
21

프로그램이 피보나치 수열의 처음 아홉 개 값을 성공적으로 계산했습니다!

파이썬 피보나치 수열: 재귀(Recursive) 접근 방식

피보나치 수열 계산은 재귀(recursion)를 활용하기에 완벽한 사례입니다. 재귀 함수란 문제를 해결하기 위해 자기 자신에게 의존하는 함수를 말합니다.

재귀 함수는 하나의 문제를 더 작은 문제들로 나눈 뒤, 자기 자신을 호출하여 해결합니다. 먼저 몇 개의 숫자를 계산할지 추적하는 변수를 초기화하겠습니다.

terms_to_calculate = 9

이 프로그램에서는 변수 하나만 초기화하면 됩니다. 다음으로 수열의 다음 숫자를 계산하는 함수를 만들어 보겠습니다.

def calculate_number(number):
    if number <= 1:
        return number
    else:
        return(calculate_number(number-1) + calculate_number(number-2))

이 함수는 전달받은 숫자가 1 이하인지 확인합니다. 1 이하라면 별도의 계산 없이 그 숫자를 그대로 반환합니다. 그렇지 않으면 calculate_number() 함수를 두 번 호출하여 목록에서 앞선 두 항목의 합을 계산합니다.

마지막으로 함수를 실행하는 메인 프로그램을 작성해야 합니다.

for number in range(terms_to_calculate):
    print(calculate_number(number))

이 루프는 terms_to_calculate 값만큼 실행됩니다. 즉, 루프는 9번 실행됩니다. 루프는 calculate_number() 메서드를 호출해 수열의 다음 숫자를 계산하고, 그 숫자를 콘솔에 출력합니다.

코드를 실행하면 다음과 같은 결과가 출력됩니다.

0
1
1
2
3
5
8
13
21

출력 결과는 앞선 반복 방식 예제와 동일합니다.

차이점은 사용한 접근 방식에 있습니다. 여기서는 수열의 다음 숫자를 계산하기 위해 스스로를 호출하는 재귀 함수를 정의했습니다. 재귀 방식은 일반적으로 반복 방식보다 로직을 이해하기 쉽기 때문에 더 선호되는 편입니다.

이 코드는 반복 예제보다 훨씬 적은 줄 수로 작성되었습니다. 게다가 프로그램이 동작하려면 변수를 하나만 초기화하면 됩니다. 반복 예제에서는 세 개의 변수를 초기화해야 했습니다.

결론

피보나치 수열은 반복 방식 또는 재귀 방식으로 생성할 수 있습니다.

반복 방식은 while 루프에 의존해 수열의 다음 숫자들을 계산합니다. 재귀 방식은 자기 자신을 호출하여 다음 숫자를 계산하는 함수를 정의하는 방식입니다.

이제 여러분도 전문가처럼 파이썬으로 피보나치 수열을 계산할 준비가 되었습니다!