public class Fib {
  public static int compteur;
  public static int fib(String prefix,int n) {
    //    System.out.println(prefix+"fib("+n+")");
    if (n==0) return 1;
    if (n==1) return 1;
    compteur++;
    return fib(prefix+" ",n-1)+fib(prefix+" ",n-2);
  }
  public static int []memo;
  public static int fibMemo(String prefix,int n) {
    //    System.out.println(prefix+"fib("+n+")");
    if (n==0) return 1;
    if (n==1) return 1;
    compteur++;
    if (memo[n-2]==0) { memo[n-2] = fibMemo(prefix+" ",n-2); }
    if (memo[n-1]==0) { memo[n-1] = fibMemo(prefix+" ",n-1); }
    return memo[n-1]+memo[n-2];
  }
  public static void main(String []a) {
    for (int i=0; i<20; i++) {
       compteur = 0;
       System.out.println("Fib("+i+")="+fib("",i)+" compteur="+compteur);
    }
    memo = new int[7]; // 0 valeur pas encore calculée, >0 valeur déjà calculée
    compteur = 0;
    System.out.println("Fib(6)="+fibMemo("",6)+" compteur="+compteur);
  }
}