Résumé : Chap 6 – La récursivité
Ce chapitre a pour objectif de présenter la récursivité comme une autre manière de répéter un traitement. Au lieu d’utiliser une boucle, une fonction récursive s’appelle elle-même pour résoudre progressivement un problème.
Le lecteur apprend à distinguer l’itération, fondée sur des structures comme for ou while, de la récursivité, qui repose sur une succession d’appels de fonction.
La récursivité est particulièrement adaptée aux problèmes qui peuvent être décomposés en plusieurs versions plus petites du même problème. Chaque nouvel appel doit ainsi rapprocher le programme d’une situation élémentaire.
Cette situation élémentaire est appelée le cas de base. Elle constitue la condition d’arrêt de la fonction et empêche les appels récursifs de se poursuivre indéfiniment.
L’exemple du compte à rebours permet de comprendre qu’une fonction récursive effectue une partie du travail, puis confie le reste à un nouvel appel utilisant une valeur plus proche du cas de base.
Le chapitre explique ensuite le rôle de la pile d’appels. Lorsqu’une fonction s’appelle elle-même, chaque appel en cours est conservé en mémoire avec les informations nécessaires pour reprendre son exécution ultérieurement.
L’exécution comporte donc généralement une phase de descente, pendant laquelle les appels s’accumulent jusqu’au cas de base, puis une phase de remontée, pendant laquelle les appels se terminent dans l’ordre inverse.
Cette compréhension permet notamment d’écrire une fonction calculant la somme des premiers entiers et d’observer comment les résultats partiels sont produits lors du dépilage des appels.
Le problème des Tours de Hanoï sert ensuite d’application complète. Pour déplacer une pile de n disques, il faut résoudre deux fois le même problème avec n - 1 disques, en déplaçant le plus grand disque entre les deux opérations.
Cet exemple montre qu’un raisonnement récursif peut traduire très directement la structure d’un problème complexe et produire un programme court, élégant et proche de la méthode de résolution.
Le chapitre souligne néanmoins que la récursivité utilise de la mémoire pour la pile d’appels et peut provoquer un nombre considérable d’opérations. Dans les Tours de Hanoï, le nombre de déplacements atteint ainsi 2n - 1.
Le but général est donc d’apprendre à reconnaître les problèmes récursifs, à définir un cas de base correct et à comprendre précisément la descente et la remontée des appels afin d’utiliser cette technique de manière maîtrisée.