[C] 재귀 함수(2), 피보나치 수열

[C] 재귀 함수(2), 피보나치수열

 

---

목차

1. 스택 메모리 영역이란? (재귀 함수 (1))

2. 재귀 함수란? (재귀 함수 (1))

3. Factorial 기능을 구현하고 싶다. (재귀 함수 (1))

3.1. Factorial 기능의 그냥 코드 구현 (재귀 함수 (1))

3.2. Factorial 기능의 함수 구현 (재귀 함수 (1))

3.3. Factorial 기능의 재귀 함수 구현 (재귀 함수 (1))

4. 피보나치수열 

4.1. 피보나치수열의 함수 구현

4.2. 피보나치 수열의 재귀 함수 구현

---

재귀 함수는 가독성이 좋고 구현이 용이하다.

편리하기는 하지만 상황에 따라 메모리 낭비가 심하기 때문에 뭐든지 적절하게 쓰는 게 중요하다. 마지막 가정 상황을 통해 한번 생각을 해볼 시간을 가질 예정이다. 일단 우리는 배우는 단계이니 일단 계속 재귀 함수에 대해 알아보자!

 

4. 피보나치 수열

 

피보나치수열은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89......  순서로 진행된다. 

앞의 두 개의 숫자를 더한 값이 다음 값이 되어 끊임없이 증가하는 수열이다.

그렇다면 피보나치의 수열에 특징에 대해 알아보자. 

 

먼저 첫 번째 수와 두 번째 수가 1, 1이라는 것이다. 이 경우를 함수로 만들 때는 규칙성이 없기 때문에 예외 처리를 한다는 것에 유의하자.

그러면 세 번째 경우(2)를 구한다고 했을 때는 몇 번을 계산해야 2라는 값이 나올까? -> 1+1 =2로 한 번에 나온다.

 

• 네 번째 경우(3)에는 1+1=2, 1+2=3 ( 1(두 번째 경우 값)+2(세 번째 경우값) =3)로 두 번에 값이 나온다.
• 다섯 번째 경우(5)에는 1+1=2, 1+2=3, 2+3=5로 세 번에 값이 나온다.
• 계속해서 해본다면 규칙을 발견할 수 있다.
• n번째 경우에는 n-2번 계산을 하면 값을 구할 수 있다.

피보나치 수열 n 번째 경우는 n-2번 계산을 통해 구할 수 있다.

---

4.1. 피보나치수열의 함수 구현

함수 부분만 스크린샷을 가져왔다.

int main() 안에서는 Fibonacci(원하는 숫자)를 넣어 함수에 num 값으로 받았다. 

아까 피보나치수열에 대해 생각하며 피보나치 수열 번째가 첫 번째, 두 번째인 경우(num==1, num==2)에는 어차피 값이 1이 나오니 1을 return 시킨다.

 

그다음에는 새로운 변수들을 추가 선언해준다. for 반복문을 통해  num-2번 동안 반복하면서 원하는 값을 구해 result에 대입하여 return 할 수 있도록 해주었다.

 

---

4.2. 피보나치 수열의 재귀 함수 구현

 

재귀 함수로 구현하자 훨씬 더 코드가 간략화되었다. 코드의 내용은 이전 피보나치수열의 함수 구현 코드를 이해했다면 재귀 함수 버전도 쉽게 이해할 수 있을 것이다. 

---

- 번외

위 피보나치 수열의 재귀 함수 구현은 실제 코드도 쉬우나 만약에 Fibonacci_re(60) 같은 큰 숫자가 들어가면 얼마만큼의 시간이 걸릴까? 개인의 컴퓨터 사양에 따라 다를 수 있지만 며칠이 지나도 수행이 끝나지 않는 엄청난 시간이 걸릴 것이다. 

또 함수가 호출될 때마다 함수 호출 횟수가 2의 승수의 합이어서 엄청나게 호출된다.

수천억 번의 함수 호출로 인해 엄청 느려질 수 있다. 

재귀 함수는 처음 말했듯이 이런 숫자가 커질수록 사용에 조심해야 한다. 적절한 상황에 재귀 함수를 잘 쓰는 것이 중요하다.

 

위 문제는 '꼬리 재귀'라는 것을 이용해 해결할 수 있다.