/* フィボナッチ数列の値を計算するプログラム
   fibo関数
   再帰を使った計算を行う
   fibo_arr関数
   再帰を使うが、計算した値を配列に保存しておき、関数が呼ばれた時点で
   計算済の値は即座にリターンすることで、呼び出し回数を削減 */
#include <stdio.h>
#include <stdlib.h>

int fibo(int);
int fibo_array(int, int *);


int main(){
  int n, i;
  int *a;

  printf("n = ");
  scanf("%d", &n);
  
  /* fibo関数による計算　*/
  printf("fibo(%d) = %d\n", n, fibo(n));

  /* fibo_arr関数による計算　*/
  /* 要素n+1個の配列の領域を確保し、初期値0を代入 */
  a = (int *) malloc( sizeof(int)*(n+1) );
  for ( i=0; i<=n; i++) a[i] = 0;

  /* 関数を呼び出してフィボナッチ数列の値を計算する */
  printf("fibo_array(%d) = %d\n", n, fibo_array(n, a));
  free( a );
  return 0;
}

int fibo(int n){
  static int count=0;

  printf("called %d times: n=%d\n", ++count, n);
  if (n==0) return 0;
  if (n==1) return 1;
  else return fibo(n-1)+fibo(n-2);
}


/* 第１引数：計算したい項  第２引数：計算結果を保存する配列の先頭アドレス */
int fibo_array(int n, int a[]){
  static int count=0;

  printf("called %d times: n=%d\n", ++count, n);

  /* a[n]の初期値には0が入っているはず。
     a[n]が0でなければ既に計算済なので、保存されていた値をリターン */
  if (a[n] != 0) return a[n];

  /* 未計算の場合、再帰で求めて、結果をa[n]に保存してからa[n]をリターン */
  if (n==0 ) {
    a[n] = 0;
    return a[n];
  }
  if (n==1 ) {
    a[n] = 1;
    return a[n];
  }
  
  else {
    a[n] = fibo_array(n-1, a)+fibo_array(n-2, a);
    return a[n];
  }
}