Séance 2
Programmation récursive avec des entiers

L'objectif de cette séance est de se familiariser avec les fonctions et procédures récursives.

Enoncés des exercices

  1. Nombres triangulaires. Écrivez une fonction récursive qui calcule la somme des n premiers nombres entiers, en commençant par 1.
    Par exemple, {Sum 6} retourne 21 = 1+2+3+4+5+6.

  2. Miroir, mon beau miroir... Il y a deux opérateurs en Oz pour faire la division des nombres entiers: div et mod.

    Écrivez une fonction récursive Mirror qui prend un entier positif n et renvoie les chiffres du nombre en ordre inverse. Par exemple, l'appel {Mirror 312} retourne 213. Considérez que n ne commence ni ne finit par 0 (zéro). Naturellement, div et mod sont utiles pour écrire cette fonction.

    Aide: utilisez un accumulateur. Quel est l'invariant satisfait par la fonction avec accumulateur?

  3. Univers parallèle (première partie). Dans un univers parallèle, l'un d'entre vous écrit ce code en réponse à la question 3. 

       declare
   fun {Foo N}
      if N<10 then 1
      else 1+{Foo (N div 10)}
      end
   end
    Sa réponse est correcte...

  4. Univers parallèle (deuxième partie). Une autre étudiante a répondu avec un code alternatif. Son code est le suivant. 

       declare
   local
      fun {FooHelper N Acc}
         if N<10 then Acc+1
         else {FooHelper (N div 10) Acc+1}
         end
      end
   in
      fun {Foo N}
         {FooHelper N 0}
      end
   end

  5. Test de primalité. Écrivez une fonction {Premier N} qui renvoie true si l'entier N est un nombre premier, false sinon. Considérez que N est premier s'il n'est divisible par aucun nombre k tel que 2 ≤ k < N.

  6. Fibonacci (première partie). Écrivez une fonction récursive qui calcule le n-ième nombre de Fibonacci, donné par la définition suivante.

    fib(0) = 1
    fib(1) = 1
    fib(n) = fib(n-1) + fib(n-2)     si n > 1

  7. Fibonacci (deuxième partie). Écrivez une nouvelle version de Fibonacci, où le nombre d'appels récursifs pour n est en O(n). Aide: utilisez une fonction avec un (ou plusieurs) accumulateur(s). Quel est l'invariant de cette fonction?

  8. Un, deux, trois, nous irons au bois (première partie). Une procédure est une suite d'instructions qui ne retourne pas de valeur. Par exemple, une procédure qui affiche un nombre n et son successeur peut être définie par 

       declare
   proc {BrowseNumber N}
      {Browse N}
      {Browse N+1}
   end

    Écrivez une procédure récursive CountDown qui reçoit un entier n et qui compte de n à 0, en affichant chaque nombre compté. Par exemple, {CountDown 3} va afficher 

       3
   2
   1
   0

  9. Un, deux, trois, nous irons au bois (deuxième partie). Considérez la procédure Count dont la définition est donnée ci-dessous. Lorsque cette procédure est appelée avec un entier n, elle affiche dans le browser les nombres 1 à n en ordre croissant. 

       declare
   proc {Count N}
      local
         proc {CountFrom I}
            if I=<N then {Browse I} {CountFrom I+1} end
         end
      in
         {CountFrom 1}
      end
   end
    Remarquez qu'une procédure récursive CountFrom est définie à l'intérieur du corps de la procédure Count. C'est cette procédure qui affiche les nombres dans l'ordre.

  10. Un, deux, trois, nous irons au bois (troisième partie). On veut maintenant modifier la définition de Count, afin que la définition de CountFrom se trouve à l'extérieur du corps de Count. Ainsi, ce n'est plus le corps mais la définition de Count qui dépend de CountFrom. La solution est toute simple: déplacer la déclaration de l'instruction local à l'extérieur de Count. 

       declare
   local
      proc {CountFrom I}
         if I=<N then {Browse I} {CountFrom I+1} end
      end
   in
      proc {Count N}
         {CountFrom 1}
      end
   end
    Mais le compilateur refuse cette définition!

Exercices supplémentaires

  1. Diviseurs et multiples. En arithmétique, on utilise fréquemment le plus grand commun diviseur entre deux nombres entiers. On peut le définir comme une fonction pgcd à deux variables entières qui satisfait les propriétés

    pgcd(m, n) = pgcd(n, m)
    pgcd(m, n) = pgcd(m+n, n)
    pgcd(m, m) = m
    De la seconde propriété, on peut dériver
    pgcd(m, n) = pgcd(r, n),     où r est le reste de la division de m par n.
    Implémentez une fonction PGCD en Oz, en utilisant ces propriétés. Cette fonction prend deux paramètres entiers. Aide: Sous quelle(s) condition(s) la propriété dérivée est-elle utile, c'est-à-dire r ≠ m ?

    Implémentez une fonction PPCM prenant deux paramètres entiers et renvoyant leur plus petit commun multiple. Réutilisez votre fonction PGCD.

  2. Numérotation des points du plan. Il existe une technique relativement simple pour affecter un entier naturel à chaque couple d'entiers naturels (x, y). La figure suivante illustre la technique, qui consiste à numéroter les diagonales successives du quart de plan. Les numéros des points sont en bleu.

    Numérotation des points du plan

    Ecrivez une fonction Numero, prenant en paramètre deux naturels x et y, et renvoyant leur numéro suivant la technique illustrée ci-dessus. Nous proposons deux techniques.

Exercice individuel (échéance: le 14 octobre 2004)

Remplissez le formulaire avec vos réponses, ensuite sélectionnez votre tuteur dans la liste. Une fenêtre apparaîtra avec le contenu d'un e-mail que vous devrez envoyer.

Sélectionnez maintenant le nom de votre tuteur dans la liste :

Boriss Mejías et Raphaël Collet - 12 octobre 2004