[C] 피보나치

// Fibonacci.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

Fibonacci.cpp

// 중복호출을 허용한 경우
#include "stdafx.h"

int count = 0;    // 호출횟수 저장용

int fib(int n)
{

 count++;
 if( n == 1 || n == 2 ) return 1;

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

}

int _tmain(int argc, _TCHAR* argv[])
{

 int n;

 while( 1 )
 {

  scanf("%d", &n);
  if( n == 0 )

break;

  count = 0;
  printf("fib(%d) = %d\n", n, fib(n));
  printf("Total call count = %d\n", count);

 }
 return 0;

}

실행 결과

// 동적 재귀 호출
#include "stdafx.h"

int count = 0;    // 호출횟수 저장용

int fib(int n)
{

 // 1.  해를 저장할 배열을 선언한다.
 static int f[100];
 
 // 2. 배열에 해가 저장되었는지 검사하고
 //  해가 저장되어 있다면 그 값을 반환
 if( f[n] )

return f[n];

 
 // 3. 계산된 결과를 반환할 때, 배열에 해를 저장하고 반환
 count++;
 if( n == 1 || n == 2 )

return f[n] = 1;

 return f[n] = fib(n-1)+fib(n-2);

}

int _tmain(int argc, _TCHAR* argv[])
{

 int n;

 while( 1 )
 {

  scanf("%d", &n);
  if( n == 0 )

break;

  count = 0;
  printf("fib(%d) = %d\n", n, fib(n));
  printf("Total call count = %d\n", count);

 }
 return 0;

}

실행결과

// 동적 비재귀 호출
#include "stdafx.h"

int count = 0;    // 호출횟수 저장용

int fib(int n)
{

 // 1. 해를 저장할 배열 선언 ( 굳이 staric 아니어도 된다. )
 int f[100];

 // 2. 초기항 설정
 f[0] = 0;
 f[1] = 1;

 // 3. 반복문을 이용하여 해를 구한다.
 for(int i = 2 ; i <= n ; i++)

  f[i] = f[i-1] + f[i-2];

 return f[n];

}

int _tmain(int argc, _TCHAR* argv[])
{

 int n;

 while( 1 )
 {

  scanf("%d", &n);
  if( n == 0 )

break;

  count = 0;
  printf("fib(%d) = %d\n", n, fib(n));
  printf("Total call count = %d\n", count);

 }
 return 0;

}

실행결과