/**
 * La transformation d'une fonction récursive un peu
 * moins triviale en sa forme récursive terminale
 * puis itérative par élimination de la récursion.
 *
 * @author JBY
 */
public class ExpoRapide {
  public static long expnonrecursif(int n,int e) {
    long r = 1;
    while (e!=0) {
      if (e%2==1) { // expostant impair
        r = n*r;
      }
      e = e/2;
      n = n*n;
    }
    return r;
  }
  public static long expterm(int n,int e,long r) {
    System.out.println("expterm("+n+","+e+","+r+")");
    if (e==0) {
      System.out.println("return "+r);
      return r;
    }
    //    if (e%2==1) { // exposant impair
    if (e%2==1) { // expostant impair
      long v = expterm(n*n,e/2,n*r);
      System.out.println("return "+v);
      return v;
    }
    else { // exposant pair
      long v = expterm(n*n,e/2,r);
      System.out.println("return "+v);
      return v;
    }
  }
  public static long expterm(int n,int e) {
    return expterm(n,e,1);
  }
  public static long exp(int n,int e) {
    System.out.println("exp("+n+","+e+")");
    if (e==0) {
      System.out.println("return 1");
      return 1;
    }
    long r = exp(n,e/2);
    if (e%2==1) { // exposant impair
      System.out.println("return "+(n*r*r));
      return n*r*r;
    }
    else { // exposant pair
      System.out.println("return "+(n*r));
      return r*r;
    }
  }

  public static void main(String[] args) {
    //    for (int i=0; i<100000000; i++) exp(5+i%1,11);
    System.out.println("5^11="+exp(5,11));
    System.out.println("5^11="+expterm(5,11));
    System.out.println("5^11="+expnonrecursif(5,11));
  }
}