[C언어] (for문과 재귀함수 이용) 피보나치 수열 구하기

 

C언어 피보나치 수열

오늘 정리할 것은 피보나치 수열이다. 이전부터 많이 만났던 피보나치 수열이지만, 재귀함수로 피보나치 수열을 만드는 데 뭔가 걸림돌이 있는 듯한 느낌을 받아 피보나치 수열에 대해 정리를 하게 되었다.

 

C언어를 이용해 원하는 곳까지의 피보나치 수열을 출력하겠다.

 

피보나치 수열이란?

 

우선 피보나치 수열이란, 첫째 및 둘째 항을 1로 두고, 그 다음 항의 값은 앞의 두 항의 합이 되는 수열이다. 첫 째 항을 1이 아닌 0으로 두기도 하며, 필자는 오늘 첫째 항을 0으로 두기로 한다.

피보나치 수열 점화식

우선, 첫 항을 0으로 두었을 때의 피보나치 수열의 점화식은 위와 같다.

 

피보나치 수열 출력 코드1 (for문)

 

우선은 for문을 이용하여 피보나치 수열을 구하도록 하겠다. 필자가 이를 구현한 코드는 아래와 같다.

for문 피보나치 수열

 i를 0부터 입력된 n이전까지 반복하며, (총 n번 반복하게 된다.) p3을 출력한다. 다만 i가 0일 때와 1일 때는 각각 0과 1을 출력하도록 예외를 둔다.

 

그 후, 점화식에 맞게, f3(세 번째 항)에 f1(첫 번째 항)과 f2(두 번째 항)을 넣은 후, 해당 값을 출력한다.

그 다음은 f2와 f3을 더해 새로운 항을 만들어야한다. 앞서 우리는 f3 = f1 + f2를 사용했다. 그러므로 f2를 f1에 대입, f3을 f2에 대입하면, 새로운 f3이 만들어진다. 

 

이 과정을 for문이 끝날 때까지 반복한다.

 

피보나치 수열 출력 코드2 (재귀함수)

 

 다음으로는 재귀함수를 이용해 피보나치 수열을 구하도록 하겠다. 사실, 피보나치 수열은 팩토리얼, 하노이 타워와 함께 재귀함수의 대표적인 예제이기도 하다. 

내가 재귀함수로 피보나치 수열을 구현한 코드는 아래와 같다.

재귀함수 피보나치 수열

우선, Fibonacci함수는 인자로 넘겨받은 번째의 피보나치 수열의 값을 출력한다. 이를테면, 3을 인자로 받으면 1을 출력한다(0 1 1이 아니다). 그러므로 0번째부터 n-1번째까지 출력하기 위하여, for문을 이용하여 인자를 전달하도록 하였다.

 

그 다음, Fibonacci함수 내부를 살펴보면, 재귀함수로 구현이 되어 있다. 재귀함수는 끝나는 지점이 있어야 정상적으로 작동하게 되는데, n이 0일때 0을 리턴, n이 1이하일 때 1을 리턴하는 것으로 함수의 종료 지점(탈출 조건)이 생긴다.

 

그 이외에는 리턴 값으로 Fibonacci(n-1) + Fibonacci(n-2)를 갖는다. 이 함수는 인자가 1이나 0이 되어 1이나 0을 리턴할 때까지 자기자신을 부르며(재귀하며) 반복된다. 재귀함수는 함수를 따라 쭉 들어갔다가 종료지점에 이르러 다시 나오는 방식으로 작동한다. 이를 그림으로 그려보면 아래와 같다.

 

피보나치 재귀함수

F(5)는 Fibonacci함수에 인자로 5를 전달한 것을 의미한다. 그것은 F(4)와 F(3)을 호출한다. 또한 각각은 인자를 -2, -1을 하며 함수를 호출한다. 그러다 F(1)에 다다르면 1을 리턴하고, F(0)에 다다르면 0을 호출한다. 그렇담 다시 위로 올라가며 값들을 더한다(Fibonnaci(n-1) + Fibonnaci(n-2)를 했기 때문). 

 

예를 들어 F(2)에는 F(1)의 값 1과 F(0)의 값 0이 더해져 1이 들어간다.

또한 F(3)은 F(2)의 값1과 F(1)의 값 1이 더해져 2가 들어간다. 

그렇담 F(4)는? F(2)와 F(3)이 더해진 3이 들어가게 된다.  이렇게 반복하면 F(5)값은 5가 나오게 된다. 

출력값

---

* 재귀 함수의 조건

1. 내가 원하는 값을 얻을 때 끝나는 조건이 있어, 재귀를 끝낼 수 있어야 함

2. 재귀 함수 속에 들어가는 인자 값이 계속 변해야 함

---