Récursivité en mode débranché

Le principe des appels récursifs est illustré par la gestion d’une pile des appels sous forme papier :

Deux types de feuilles sont nécessaires :

• la feuille du premier appel qui contient une dernière case permettant d’obtenir le résultat final ;
• la feuille des appels récursifs.

Chaque fois que la condition d’arrêt (case “A”) n’est pas atteinte, on remplit la case “B”. La feuille actuelle est ensuite posée sur la pile des feuilles précédemment posées (contenant en fond de pile le premier appel), puis une nouvelle feuille est prise.

La phase de renvoi est gérée par la case “C”. Une fois le dépliement totalement réalisée, la feuille d’appel est au sommet de la pile : on obtient le résultat final.

Deux exemples sont fournis ainsi qu’un document général permettant de construire sa propre situation.

Activité 1 : la dichotomie

Recherche d’une valeur dans un tableau trié.

Activité 2 : les poupées Matriochka

Recherche d’un nombre de poupées imbricables à partir d’une hauteur maximale.

Document général

Par ailleurs, des documents modifiables sont fournis permettant de s’adapter à d’autres situations d’appels récursifs.