Raisonnement par récursion

Version imprimable

25/03/2016, 17h53
lionelus

Raisonnement par récursion

Bonjour,

J'ai beaucoup de mal à comprendre les raisonnements récursifs comme les tours de hanoi ou le triangle de sierpinski.

Est ce qu'il existe une méthode ou une démarche générale pour pouvoir les résoudre ?

Merci par avance.

Bonjour,

Sujet difficile mais néanmoins important: la récursion permet sur certains sujet des solutions très élégantes!

Voilà un petit exemple pour initier le sujet: l'affichage d'une structure arborescente.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 def parcours_arbre(arbre, niv=0): """affichage des éléments d'un arbre (liste de listes de listes...) """ for elem in arbre: if isinstance(elem, list): niv += 2 parcours_arbre(elem, niv) niv -= 2 else: print(" "*niv, elem) L = [1, [2,3,[4,5],6,7],8,[9]] parcours_arbre(L)
Ce qui affiche:
Code:

1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
On voit bien que l'arbre a été parcouru complètement, et que l'indentation des éléments affichés est bien en rapport avec la "profondeur" de ces éléments.

Pour le code, on voit bien à quel moment on ré-appelle la fonction dans laquelle on se trouve et pourquoi.

Quelques tests sur ce code devraient déjà débroussailler le sujet.

Il y a bien sûr des compléments pour résoudre des problèmes plus complexes! Voir par exemple https://fr.wikipedia.org/wiki/Algorithme_r%C3%A9cursif.

Bon courage!

26/03/2016, 14h14
lionelus

Merci pour votre réponse.
Là où j'ai le plus de mal à comprendre la récursivité c'est quand on appelle plusieurs fois la fonction au sein de cette fonction. Je n'arrive pas à me représenter ce que fait chaque appel.
26/03/2016, 15h20
tyrtamos

Mais c'est très facile avec Python de mettre des "print" dans le code pour voir l'évolution des données pendant l'exécution! C'est souvent comme ça qu'on peut comprendre le fonctionnement d'un algorithme compliqué.

La démarche générale, pour la conception d'un algorithme récursif, est de se ramener à une ou plusieurs instances plus simple/plus petite du problème. On fait l'hypothèse qu'on possède déjà une solution pour résoudre la version plus simple, et à partir de là, on trouve un moyen d'étendre cette solution à une instance plus complexe. C'est une généralisation du principe mathématique de raisonnement par récurrence.

Les tours de Hanoi sont un bon exemple car la solution récursive est particulière simple:

On suppose qu'on a déjà une solution pour déplacer une tour de n disques sur un autre plot.
Il est facile de l'étendre à n+1 disques:

on déplace les n premiers disques sur le plot intermédiaire (solution connue par hypothèse)
on déplace le dernier disque sur le plot final
on déplace à nouveau les n premiers disques sur le plot final (solution connue par hypothèse)

Quelle est cette mystérieuse solution connue par hypothèse ? Et bien c'est la même, en soustrayant 1 de n (c'est l'appel récursif; il y en a deux ici).
Evidemment, on ne peut réduire la taille du problème indéfiniment, il faut donc un case de base (parfois plusieurs) qui puisse être résolu directement.
Ici on peut prendre le cas n = 0: s'il n'y a aucun disque a déplacer, la solution est donc trivialement de ne rien faire. On pourrait aussi s'arrêter à n = 1, la solution est presque aussi simple, c'est un autre choix possible pour le cas de base.

Au niveau du codage, il faut ici réfléchir à ce qu'on a besoin de passer comme information à la fonction récursive; le rôle de chaque plot (départ/arrivée/intermédiaire) n'est pas fixe mais change à chaque appel récursif; il faut donc, d'une façon ou d'une autre, passer cette information.
Par exemple:
Code:

1 2 3 4 5 def hanoi(n, depart, arrivee, inter): if n > 0: hanoi(n-1, depart, inter, arrivee) print("Déplacer le disque {n} de {depart} à {arrivee}".format(**locals())) hanoi(n-1, inter, arrivee, depart)
Le principal avantage des solutions récursives, c'est qu'elles sont généralement simples et naturelles (quand on s'y est un minimum habitué). Cette simplicité fait que l'implémentation est souvent facile, le code est lisible, et les chances de faire une erreur sont limitées. Le principal désavantage est que l'utilisation de la pile les rendent souvent non optimales lorsqu'une solution itérative est possible, surtout dans des languages (comme Python) qui n'optimisent pas la récursion terminale.