7. Compléments sur la Récursivité

1 Exercice 7.3.1

a) Un prédicat n’est autre qu’une fonction dont le résultat est booléen : ce ne peut être que true ou false.

ERRATUM : Le livre se trompe dans les exemples, la place du prédicat est incorrecte, il doit être en dernière position et non en première !

Le cas a > b laisse certains étudiants perplexes. En fait, si a > b, l’intervalle [a,b] est vide, et les éléments de l’ensemble vide possèdent toutes les propriétés du monde. Ce sont par exemple tous des livres écrits en 1217, comme vous le vérifierez en raisonnant par l’absurde :-)

b) Les entiers étant petits, on peut utiliser le prédicat premier? de l’exercice 6.8.13 :

c) Analogue à la question a). Même ERRATUM sur la position du prédicat dans les exemples...

d) Erreur naïve : la négation d’un prédicat p n’est pas (not p) car p n’est pas un booléen. Attention au typage ! Il s’agit en fait de... de quoi ? Ce doit être un prédicat !

2 Exercice 7.3.2

a) Il suffit d’introduire une fonction locale (iter a acc) avec deux variables de boucle [les autres ne varient pas]. Attention, l’accumulateur acc est à gauche, ceci n’a d’importance que si l’opérateur op n’est pas commutatif.

b) En une ligne :

3 Exercice 7.3.3

Je vous conseille, si vous êtes matheux, à jeter un oeil sur Mathematica, très beau système, hélas un peu onéreux...

a) Nest et FixedPoint sont des primitives de Mathematica...

ERRATUM : l’exemple du livre a tort d’utiliser le signe =. Il n’y aura jamais stricte égalité. Il faut passer un prédicat d’égalité approchée :

c) x = 1 + 1/x <==> x2-x-1 = 0. On cherche la solution > 0.

4 Exercice 7.3.4

Typiquement l’exercice qu’il faut faire seul pour être content de soi, alors je ne vais pas gâcher votre plaisir... On suppose que la dérivée de f ne s’annulle en aucun point dans le domaine d’étude [géométriquement, pas de tangente horizontale !]. D’où vient la transformation de l’approximation a en une meilleure approximation a - f(a)/f’(a) ? Simplement de l’équation de la tangente à la courbe de f au point d’abscisse a. La technique de Newton consistait à trouver l’intersection de cette tangente en M(a;f(a)) avec l’axe Ox, obtenant ainsi une approximation meilleure que a. La convergence vers une solution de f(x) = 0 est rapide.

5 Exercice 7.3.5

a) Exercice sur l’épluchage des chiffres d’un entier n par divisions successives... Le chiffre des unités en base b s’obtient par (modulo n b). Le nombre privé du chiffre des unités n’est autre que (quotient n b).

b) Je vous la laisse...

c) Il faut faire abstraction des calculs effectués dans les deux fonctions précédentes, et les passer en paramètres dans une version plus générale...

6 Exercice 7.3.6

Passer en CPS revient à prendre en main la suite des calculs. Nommons f la continuation courante. Il s’agit donc maintenant de calculer [de manière automatiquement itérative] l’image par f du nombre de serrements de main parmi n convives :

b) Les continuations peuvent avoir plusieurs paramètres. Ici (k-bezout a b f) calcule f(g,u,v) où g est le PGCD de a,b et u,v des coefficients de Bezout : g = au+bv.

c) Une fonction est itérative si et seulement si sa transformation en CPS laisse invariante la continuation courante :

7 Exercice 7.3.7

a) Je commence par définir la structure de couple. Le couple résultat n’est construit qu’à la fin.

b) La récurrence enveloppée traîne les couples intermédiaires :

c) La version CPS.

Dans le dernier exemple ci-dessus, on notera le style CPS, préférable à un style semi-direct :

8 Exercice 7.3.8

a) ERRATUM : la fonction à programmer est (k-fib n f) == (f (fib n) (fib (+ n 1)))

b) Passez directement en paramètres les entiers a = fib(n) et b = fib(n+1)...