Comprendre la récursivité

[sozary]

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:

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 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

Code : Tout sélectionner

$txt&=@CRLF&$n

Donc comme notre $n vaut 0, on aura en fait:

Code : Tout sélectionner

$txt&=@crlf&"0"

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:

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)

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:

Code : Tout sélectionner

p(4-2)
$txt&=@CRLF&"4"
p(4-1)

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:

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

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.

[jchd]

La récursivité en une seule ligne

[matwachich]

jchd

[jchd]

Désolé de cette petite crotte, j'ai pas pu résister à la pression. Faudra faire passer la voirie après...

[sozary]