재귀의 활용 : Fibonacci Sequence

재귀함수는 이해하는 것도 중요하지만 잘 정의하는 것도 중요하다. 그리고 재귀함수를 잘 정의하기 위해서는 사고의 전환이 필요하다.

# 피보나치 수열: Fibonacci Sequence

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값

피보나치 수열의 n번째 위치의 값을 반환하는 함수는 수학적으로 다음과 같이 표현이 된다.

int Fib(int n)

{

if(n == 1)

return 0;

else if(n == 2)

return 1;

else

return Fib(n-1)+Fib(n-2);

}

여기서 중요한 것은 수학적 재귀의 표현이 그대로 코드로 옮겨졌으음을 인식하는 것이다.

※ 시간이 지나서 재귀함수에 익수해지면 누구나 함수의 호출순서에 신경을 쓰지 않게 된다.

위에서 보이듯이 피보나치 수열의 7번째 값의 출력을 위해서 25회의 함수호출이 동반되었다. 

때문에 성능상의 불리함은 분명 존재한다.

+ 연산자의 왼편에 있는 Fibo 함수호출이 완료되어야 비로소 + 연산자의 오른편에 있는 Fibo 함수호출이 진행이 된다.