Chapitre 5 : Les Types de Récursivité et Exercices

IV. Types de récursivité

Il existe plusieurs types de récursivité selon la structure des appels :

Récursivité simple (ou linéaire) : Un algorithme récursif est simple s’il résout chaque cas avec au plus un appel récursif. Le calcul de la factorielle en est un exemple typique.
Récursivité multiple : Un algorithme récursif est multiple si l’un des cas qu’il distingue se résout avec plusieurs appels récursifs en cascade. Si “plusieurs = 2”, on parle de récursivité binaire. Les tours de Hanoï ou la suite de Fibonacci native sont des problèmes qui se résolvent en récursivité binaire.
Récursivité croisée (ou mutuelle) : Deux algorithmes sont mutuellement récursifs si l’un fait appel à l’autre et l’autre fait appel à l’un.
Récursivité terminale : Un algorithme est récursif terminal si l’appel récursif est la toute dernière instruction de la fonction (sans opération supplémentaire au retour, comme l’ajout de +1 par exemple). La valeur retournée est directement obtenue par l’appel récursif, ce qui permet à de nombreux compilateurs et interpréteurs d’optimiser en évitant de surcharger la pile d’appels.
Récursivité imbriquée : Un algorithme est récursif imbriqué si l’appel récursif est utilisé lui-même comme paramètre pour un autre appel récursif. La fonction d’Ackermann en est un exemple.

Exercice 1 : Écrire une fonction récursive qui retourne la somme des chiffres d’un entier N donné. Exemples : 123 implique 1+2+3 = 6.
Exercice 2 : Écrire une fonction récursive qui calcule le factoriel d’un entier N positif.
Exercice 3 : Écrire une fonction récursive qui examine si un entier N saisi au clavier est un nombre premier ou non. (Indications : on peut vérifier les diviseurs via une fonction auxiliaire avec paramètre).
Exercice 4 : Écrire une fonction récursive qui permet de calculer la suite de Fibonacci donnée par f(n) = f(n-1) + f(n-2).
Exercice 5 : Écrire une fonction récursive simple qui calcule la puissance x^n (x et n étant des entiers positifs).