/* フィボナッチ数列の値を計算するプログラム
   再帰を使ってシンプルに書いたが、同じ値の呼び出しを何度も行うので、
   非常に無駄が多い */
#include <stdio.h>

int fibo(int);


int main(){
  int n;

  printf("n = ");
  scanf("%d", &n);
  
  printf("fibo(%d) = %d\n", n, fibo(n));
  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);
}