longueur(L)

/* longueur(L)

 *
 * Profil:
 * =======
 *   liste -> entier
 *
 * Exemples:
 * =========
 *   longueur( () ) = 0
 *   longueur( (a) ) = 1
 *   longueur( (a b c) ) = 3
 *                       = 1 + longueur( (b c) )  // (b c) = reste( (a b c) )
 *                       = 1 + 1 + longueur( (c) )
 *                       = 1 + 1 + 1 + longueur( () )
 *                       = 1 + 1 + 1 + 0
 *                       = 3
 *
 * Axiomes:
 * ========
 *
 *   longueur( () ) = 0
 *   longueur( cons(x, L) ) = 1 + longueur(L)
 *
 * Algorithme récursif:
 * ====================
 * fonction longueur(L: liste): entier
 * debut
 *  | l: entier
 *  | l:= 0
 *  | si est_vide(L)
 *  |  | alors l:= 0
 *  |  | sinon l:= 1+longueur(reste(L))
 *  | finsi
 *  | retourner l
 * fin
 *
 * Algorithme itératif:
 * ====================
 * fonction longueur(L: liste): entier
 * debut
 *  | l: entier
 *  | l:= 0
 *  | tant que non est_vide(L) faire
 *  |  | l:= l+1           // L non vide, on ajoute 1
 *  |  | L:= reste(L)      // passage au suivant: on enleve le premier element de la liste L
 *  | fin tant que
 *  | retourner l
 * fin
 *
 */

#include "liste.h"

int longueurR(liste L)
{
  int l = 0;

  /* on simplifie l'algorithme: si L est vide, alors pas besoin de refaire l:= 0 */
  if (!est_vide(L))
  {
    l = 1 + longueurR(reste(L));
  }
  return l;
}

int longueurI(liste L)
{
  int l = 0;
  while (! est_vide(L))
  {
    l = l+1;
    L = reste(L);
  }
  return l;
}

int main()
{
  /* test de longueurR et longueurI */
  liste L1 = l_vide();
  L1 = cons(1, L1);
  L1 = cons(5, L1);
  L1 = cons(2, L1);
  L1 = cons(3, L1);
  L1 = cons(1, L1);
  printf("longueur de ");
  affichage(L1);
  printf("= %d (recursif) %d (iteratif) \n", longueurR(L1), longueurI(L1));
}