Comprendre la récursivité

Espace contenant des tutoriels divers concernant AutoIt.
Règles du forum
.

Tutoriel "La programmation avec Autoit" : https://openclassrooms.com/fr/courses/1 ... vec-autoit
Répondre
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Comprendre la récursivité

#1

Message par 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:

Image(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 :wink: !





Donc voilà! Vous êtes un professionnel de la fonction récursive à présent!
Si vous avez des questions, n'hésitez pas à les signaler.
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : En ligne

Re: Comprendre la récursivité

#2

Message par jchd »

La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
matwachich
Membre émérite
Membre émérite
Messages : 986
Enregistré le : lun. 19 oct. 2009 04:04
Localisation : Algérie
Status : Hors ligne

Re: Comprendre la récursivité

#3

Message par matwachich »

jchd :wink: :D
Sortons VW du coté obscure! - La curiosité est un vilain défaut! Cliquez ici
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : En ligne

Re: Comprendre la récursivité

#4

Message par jchd »

Désolé de cette petite crotte, j'ai pas pu résister à la pression. Faudra faire passer la voirie après...
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: Comprendre la récursivité

#5

Message par sozary »

:mrgreen: :mrgreen:
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Répondre