/* Recursivite en arbre n-aire parfait         */

public class RecursiviteEnArbreParfait {

/////////////////////////////////////////////////

/* Parcours recursif en arbre unaire           */
/* de profondeur n                             */

  static int parcoursUnaire(int n) {
    int nb = 1;
    if ( n > 0 ) {
      nb = nb+parcoursUnaire(n-1); }
    return nb;
  }

/* Parcours recursif en arbre binaire parfait  */
/* de profondeur n                             */

  static int parcoursBinaire(int n) {
    int nb = 1;
    if ( n > 0 ) {
      nb = nb+parcoursBinaire(n-1);
      nb = nb+parcoursBinaire(n-1); }
    return nb;
  }

/* Parcours recursif en arbre ternaire parfait */
/* de profondeur n                             */

  static int parcoursTernaire(int n) {
    int nb = 1;
    if ( n > 0 ) {
      nb = nb+parcoursTernaire(n-1);
      nb = nb+parcoursTernaire(n-1);
      nb = nb+parcoursTernaire(n-1); }
    return nb;
  }

/////////////////////////////////////////////////
  
/* Programme principal                         */

  public static void main(String [] args) {
    int n;
    int nb;
    { Ecran.afficher("Niveau en unaire? ");
      n = Clavier.saisirInt();
      nb = parcoursUnaire(n);
      Ecran.afficherln("Nombre d'appels : ",nb); }
    Ecran.sautDeLigne();
    { Ecran.afficher("Niveau en binaire? ");
      n = Clavier.saisirInt();
      nb = parcoursBinaire(n);
      Ecran.afficherln("Nombre d'appels : ",nb); }
    Ecran.sautDeLigne();
    { Ecran.afficher("Niveau en ternaire? ");
      n = Clavier.saisirInt();
      nb = parcoursTernaire(n);
      Ecran.afficherln("Nombre d'appels : ",nb); }
  }
}