class Rec {
  static int Fib(int n) {
  // \esc{Fibonacci, voir page \pageref{prog:fib}}

    if (n <= 1)
        return 1;
    else
        return Fib (n-1) + Fib (n-2);
  }

  static int Fact(int n)  {
  // \esc{Factorielle, voir page \pageref{prog:fact}}

    if (n <= 1)
        return 1;
    else
        return n * Fact (n-1);
  }

  static int C(int n, int p)  {
    // \esc{Triangle de Pascal, voir page \pageref{prog:triangle-de-pascal}}

    if ((n == 0) || (p == n))
        return 1;
    else
        return C(n-1, p-1) + C(n-1, p);
  }

  static int FibIter(int n)  {
  // \esc{Fibonacci itératif, voir page \pageref{prog:fib-iteratif}}

    int u, v;
    int u0, v0;
    int i;

    u = 1; v = 1;
    for (i = 2; i <= n; ++i) {
        u0 = u; v0 = v;
        u = u0 + v0;
        v = v0;
    }
    return u;
  }

  static int Ack(int m, int n) {
  // \esc{La fonction d'Ackermann, voir page \pageref{prog:ackermann}}

    if (m == 0)
        return n + 1;
    else
        if (n == 0)
            return Ack (m - 1, 1);
        else
            return Ack (m - 1, Ack (m, n - 1));
  }

  static int f(int n)  {
  // esc{La fonction 91, voir page \pageref{prog:fn-91}}

    if (n > 100)
        return n - 10; 
    else
        return f(f(n+11));        
  }

  static int g(int m, int n) {
  // \esc{La fonction de Morris, voir page \pageref{prog:fn-morris}}

    if (m == 0)
        return 1; 
    else
        return g(m - 1, g(m, n));      
  }

  static void Hanoi(int n, int i, int j)  {
  // \esc{Les tours de Hanoi, voir page \pageref{prog:hanoi}}

    if (n > 0) {
        Hanoi (n-1, i, 6-(i+j));
        System.out.println (i + " -> " + j);
        Hanoi (n-1, 6-(i+j), j);
    }
  }

  static void Dragon(int n, int x, int y, int z, int t) {
  // \esc{La courbe du dragon, voir page \pageref{prog:dragon}}
    int u, v;

    if (n == 1) {
//        MoveTo (x, y);
//        LineTo (z, t);
    } else {
        u = (x + z + t - y) / 2;
        v = (y + t - z + x) / 2;
        Dragon (n-1, x, y, u, v);
        Dragon (n-1, z, t, u, v);
    }
  }

  static void DragonUn(int n, int x, int y, int z, int t)  {
  // \esc{La courbe du dragon, voir page \pageref{prog:dragon-2}} */
    int u, v;

    if (n == 1) {
//        MoveTo (x, y);
//        LineTo (z, t);
    } else {
        u = (x + z + t - y) / 2;
        v = (y + t - z + x) / 2;
        DragonUn (n-1, x, y, u, v);
        DragonBis (n-1, u, v, z, t);
    }
  }

  static void DragonBis(int n, int x, int y, int z, int t)  {

    int u, v;

    if (n == 1) {
//        MoveTo (x, y);
//        LineTo (z, t);
    } else {
        u = (x + z - t + y) / 2;
        v = (y + t + z - x) / 2;
        DragonUn (n-1, x, y, u, v);
        DragonBis (n-1, u, v, z, t);
    }
    
  }

  public static void main (String args[]) {

    System.out.println (Fib (3));
    System.out.println (Fact (3));
    System.out.println (C (3, 2));
    System.out.println (FibIter (3));
    System.out.println (Ack (2, (Ack (1,1))));
    System.out.println (f (3));
    Hanoi (3, 1, 3);
  }
}