Comprendre la récursivité
Posté : ven. 28 août 2015 14:25
Bonjour!
Jbnh avait posté un tutoriel sur les fonctions récursives.
Il a aidé de nombreuses personnes, mais comment analyser le fonctionnement de telles fonctions et prévoir ce qu'elles renvois?
C'est ce que je vous propose ici d'apprendre à faire!
I) Une fonction récursive simple
Qui dit fonction récursive dit fonction qui s'appelle elle-même. Il y en a de plusieurs types, permettant de réaliser par exemple des fractales ou des tris, l'article sur wikipédia à ce sujet vous éclaircira d'avantage.
Un exemple de fonction récursive:
Avec cette fonction affiche, on peut très facilement prédire le résultat, contenu ici dans la variable $txt.
avec affiche(5), comme 5>0, affiche(5-1) va s’exécuter, et ce jusqu'à ce que $n vaut 0.
Ensuite on a
Donc comme notre $n vaut 0, on aura en fait:
Par la suite, notre fonction va s'arrêter, on retourne donc à la même fonction, mais avec n valant 1 cette fois-ci et ainsi de suite.
Le résultat final contenu dans $txt est donc:
II) Une fonction récursive complexe
Le résultat du programme que nous venons de réalisé était facile à deviner, mais d'autre résultats de fonctions récursives sont moins facile à deviner:
Le double usage de la récursivité pose ici problème.
Je vais vous proposer deux méthodes afin d'anticiper le résultat de cette fonction récursive p($n).
II.a) L'analyse descendante
Cette méthode est la plus longue et la plus fastidieuse, mais appliquée rigoureusement, conduit au résultat.
On commence par étudier le premier appel que l'ont fait à notre fonction p($n):p(4).
Si on remplace notre n par la valeur 4 dans le code, on a:
Nous allons faire pareil pour les appels p(4-2) donc p(2) et p(4-1) donc p(3).... La représentation va prendre l'allure d'un arbre:
(Cliquez pour agrandir)
Si on lit notre arbre, on voit bien que notre p(2) quand il est appelé appel à son tour p(0), ajoute "2" à $text, et appel ensuite p(1), et ainsi de suite.
Les appels ont lieu si n>0, il n'y a donc pas d'appel pour n=-1 et n=0. A chaque fois qu'il n'y a plus d'appel récursif, la suite des instructions de l'appel courant est effectuée, c'est à dire l'ajout de @crlf&n à la variable $txt.
L'arbre va se lire de gauche à droite.
Les cases où j'ai mis par exemple 4,2,3 ou 1 représente l'ajout de cette valeur à $txt.
On peut donc lire 2 1 4 1 3 2 1.
Avec cette méthode on voit que des sous-arbres se répètent, ce sont les appels de p(1).
II.b) L'analyse ascendante
Cette méthode est est plus rapide si on a bien lu la fonction p au préalable.
Donc cette fois nous allons partir à l'inverse, par le bas avec le dernier appel récursif possible lorsque $n=1 et nous allons remonter ensuite pour la valeur immédiatement supérieure. Ce qui donne:
Vous voyez, pas si compliqué en fin de compte! Le plus "complexe" en fin de compte est de savoir quel est le dernier appel récursif possible, pas très dure si on a bien lu la fonction !
Donc voilà! Vous êtes un professionnel de la fonction récursive à présent!
Si vous avez des questions, n'hésitez pas à les signaler.
Jbnh avait posté un tutoriel sur les fonctions récursives.
Il a aidé de nombreuses personnes, mais comment analyser le fonctionnement de telles fonctions et prévoir ce qu'elles renvois?
C'est ce que je vous propose ici d'apprendre à faire!
I) Une fonction récursive simple
Qui dit fonction récursive dit fonction qui s'appelle elle-même. Il y en a de plusieurs types, permettant de réaliser par exemple des fractales ou des tris, l'article sur wikipédia à ce sujet vous éclaircira d'avantage.
Un exemple de fonction récursive:
Code : Tout sélectionner
Global $txt=""
Func affiche($n)
if ($n>0) Then
affiche($n-1)
EndIf
$txt&=@CRLF&$n
EndFunc
affiche(5)
MsgBox(0,"",$txt)
avec affiche(5), comme 5>0, affiche(5-1) va s’exécuter, et ce jusqu'à ce que $n vaut 0.
Ensuite on a
Code : Tout sélectionner
$txt&=@CRLF&$n
Code : Tout sélectionner
$txt&=@crlf&"0"
Le résultat final contenu dans $txt est donc:
Code : Tout sélectionner
0
1
2
3
4
5
II) Une fonction récursive complexe
Le résultat du programme que nous venons de réalisé était facile à deviner, mais d'autre résultats de fonctions récursives sont moins facile à deviner:
Code : Tout sélectionner
Func p($n)
If($n>0) Then
p($n-2)
$txt&=@CRLF&$n
p($n-1)
EndIf
EndFunc
p(4)
MsgBox(0,"",$txt)
Je vais vous proposer deux méthodes afin d'anticiper le résultat de cette fonction récursive p($n).
II.a) L'analyse descendante
Cette méthode est la plus longue et la plus fastidieuse, mais appliquée rigoureusement, conduit au résultat.
On commence par étudier le premier appel que l'ont fait à notre fonction p($n):p(4).
Si on remplace notre n par la valeur 4 dans le code, on a:
Code : Tout sélectionner
p(4-2)
$txt&=@CRLF&"4"
p(4-1)
(Cliquez pour agrandir)
Si on lit notre arbre, on voit bien que notre p(2) quand il est appelé appel à son tour p(0), ajoute "2" à $text, et appel ensuite p(1), et ainsi de suite.
Les appels ont lieu si n>0, il n'y a donc pas d'appel pour n=-1 et n=0. A chaque fois qu'il n'y a plus d'appel récursif, la suite des instructions de l'appel courant est effectuée, c'est à dire l'ajout de @crlf&n à la variable $txt.
L'arbre va se lire de gauche à droite.
Les cases où j'ai mis par exemple 4,2,3 ou 1 représente l'ajout de cette valeur à $txt.
On peut donc lire 2 1 4 1 3 2 1.
Avec cette méthode on voit que des sous-arbres se répètent, ce sont les appels de p(1).
II.b) L'analyse ascendante
Cette méthode est est plus rapide si on a bien lu la fonction p au préalable.
Donc cette fois nous allons partir à l'inverse, par le bas avec le dernier appel récursif possible lorsque $n=1 et nous allons remonter ensuite pour la valeur immédiatement supérieure. Ce qui donne:
Code : Tout sélectionner
p(1): p(-1) 1 p(0) soit 1
p(2): p(0) 2 p(1) soit 2 1
p(3): p(1) 3 p(2) soit 1 3 2 1
p(4): p(2) 4 p(3) soit 2 1 4 1 3 2 1
Donc voilà! Vous êtes un professionnel de la fonction récursive à présent!
Si vous avez des questions, n'hésitez pas à les signaler.