/**
 * Un programme illustrant l'élimination de la récursion du calcul de la
 * factorielle.
 */
public class Fact {
  /**
   * Cette fonction est la version condensée de la solution 4.
   * Exercice: transformer le while en for...
   */
  public static int fact5(int n) {
    int r = 1;
    while (n!=0) {
      r = n*r;
      n = n-1;
    }
    return r;
  }
  /**
   * Cette fonction est la version itérative du calcul de la factorielle
   * obtenue par transformation élémentaire du calcul récursif terminal.
   * En effet, dans ce dernier, puisque l'appel est le dernier et qu'on ne
   * fait plus rien des arguments après l'appel, il est possible de replacer
   * l'appel par une boucle en arrière (ici un while) avec une modification des
   * arguments (plutôt que de les remplacer par des nouvelles variables, 
   * réutiliser les anciennes en les modifiant).
   */
  public static int fact4acc(int n,int r) {
    while (n!=0) {
      r = n*r;
      n = n-1;
    }
    return r;
  }
  public static int fact4(int n) {
    return fact4acc(n,1);
  }
  public static int fact3acc(int n,int r) {
    if (n==0) return r;
    return fact3acc(n-1,n*r);
  }
  /**
   * Cette fonction n'est que la version épurée (sans les affichages) de la
   * version récursive terminale de la factorielle.
   */
  public static int fact3(int n) {
    return fact3acc(n,1);
  }
  public static int fact2acc(int n,int r,String prefixe) {
    System.out.println(prefixe+"fact2acc("+n+","+r+")");
    if (n==0) {
      System.out.println(prefixe+"return "+r);
      return r;
    }
    int v = fact2acc(n-1,n*r,prefixe+" ");
    System.out.println(prefixe+"return "+v);
    return v;
  }
  /**
   * Cette fonction appelle la fonction récursive terminale du calcul de
   * la factorielle.
   * L'idée est d'ajouter un argument contenant les calculs partiels de
   * la factorielle.
   * On observera les sorties afin de constater que le calcul est obtenu de
   * façon bien différente de l'autre version naïve...
   * Ce qui nous autorise à faire cette transformation est le fait que
   * la multiplication est commutative.
   */
  public static int fact2(int n) {
    return fact2acc(n,1,"");
  }
  /**
   * La définition naïve de la factorielle par récursion.
   * Cette définition n'est pas récursive terminale.
   * Une récursive terminale est une fonction dans laquelle, hormis les
   * instructions de retour (return), la dernière instruction exécutée est
   * un appel récursif.
   * Ici, APRÈS l'appel récursif, le résultat est utilisé dans une
   * multiplication.
   */
  public static int fact(int n,String prefixe) {
    System.out.println(prefixe+"fact("+n+")");
    if (n==0) {
      System.out.println(prefixe+"return 1");
      return 1;
    }
    int v = fact(n-1,prefixe+" ");
    System.out.println(prefixe+"return "+n+"*"+v);
    return n*v;
  }
  public static void main(String []args) {
    System.out.println("récursion naïve 10!="+fact(10,""));
    System.out.println("récursion terminale 10!="+fact2(10));
    System.out.println("récursion terminale (version propre) 10!="+fact3(10));
    System.out.println("élimination de la récursion 10!="+fact4(10));
  }
}