Python을 이용한 피보나치 수열 출력하기

피보나치 수열이란 무엇인가 ?

1  1  2  3  5  8  13  21  34 
처럼 N번째 수는 N-1 번째와 N-2번째의 합으로 결정됩니다.  우리는 Python을 이용해서 
재귀함수와 반복문을 통해서 구해보도록 하겠습니다.
먼저 재귀 함수입니다.

재귀함수

재귀 함수를 이용한 코딩법은 간단하게 나타낼수 있지만 값이 크면 클수록 원하는 값을 구하는데 시간이 오래걸린다는 단점이 있습니다.

재귀함수를 이용하면 컴퓨터는 위의 방법을 통해 값을 찾습니다 함수의 N값이 1 이나 2 가나올때 까지 게속 스스로의 재귀를 하면서 return 하는 방법이다. 문법으로는 표현하기는 쉽지만 값이 커지면 커질수록 실행하는 속도가 제곱으로 속도가 오래걸린다는 단점이있다.

반복문을 이용한 피보나치 수열

 

다음은 반복문을 이용한 피보나치 수열의 출력법입니다. 재귀는 표현하기는 쉽지만 값이 클수록 구하는 시간이 오래걸린다는 단점이 있습니다. 같은 문제라도 반복문을 이용하면 아무리 큰수라도 수를 금방 구할수있습니다.
위의 프로그램을 잠시 살펴 보겠습니다.

우리는 피보나치 수열을 구하기위해선 n-1번째 값과 n-2값을 두개를 더해야합니다.
그러므로 반복문을 통해서 n-2 값을 pi_1 에 n-1값을 pi_2 에 저장합니다. 
pi_2 = pi_1 + pi_2 // 라는 식에서 오른쪽 pi_2는 n-1값이고 왼쪽의 pi_2는 n번재값 이라는걸 조금만 생각해보면 알수있습니다.

반복문을 이용하면 재귀함수로는 오래걸리는 값도 빠르게 연산이 가능합니다.