[Tuto] Les fonctions récursives

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
jbnh
Modérateur
Modérateur
Messages : 1932
Enregistré le : ven. 02 mai 2008 13:54
Localisation : Bruxelles
Contact :
Status : Hors ligne

[Tuto] Les fonctions récursives

#1

Message par jbnh » ven. 18 juin 2010 00:11

1 - Introduction et exemples
2 - Les vecteurs et diviser pour mieux résoudre
3 - Le tri rapide (Quicksort)
4 - Le Backtracking

Débat des membres

"En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique."
Wikipedia.org
En clair, la récursivité c'est de la récurrence. Dans une fonction, on rappelle cette même fonction et les variables varient dans les paramètres. Le but est, entre-autres, d'éviter les boucles.

Voici un premier exemple concret facile :

Code : Tout sélectionner

Const $MAX = 10

FonctionRecursive(0)

Func FonctionRecursive($res)  
    If $res <= $MAX Then
        msgbox(0,"Nombre", $res)    
        FonctionRecursive($res+1)
    Endif
EndFunc
Vous verrez également qu'on peut très vite se triturer le cerveau, mais mon Dieu, que c'est magnifique :

Code : Tout sélectionner

$resultat = FonctionFactorielle(5)
msgbox(0,"",$resultat) ; retourne 120 : 5*4*3*2*1*1

Func FonctionFactorielle($n)  
    local $res
    If $n=0 Then ; la factorielle de 0 est 1
                      ; condition de sortie
        $res = 1
    Else
        $res = $n*FonctionFactorielle($n-1)     
    Endif
    
    return $res
EndFunc
Voici comment ça marche : Dans la fonction existe une condition de sortie, c'est If $n=0 . En clair on décrémente n jusqu'à ce que cette variable vaille 0. Donc d'abord, $n vaut 5 et res 5*FonctionFactorielle(4) etc. Ce raisonnement équivaut à remplacer :
$res = $n*FonctionFactorielle($n-1) par
$res = $n*FonctionFactorielle(4)*FonctionFactorielle(3)*FonctionFactorielle(2)*FonctionFactorielle(1)*FonctionFactorielle(0) soit 5*4*3*2*1*1.

N'hésitez pas à regarder l'image en attaché si vous avez encore quelques problèmes de compréhension.
Fichiers joints
recursion-normal.png
recursion-normal.png (47.31 Kio) Vu 6881 fois
recursion-normal.png
recursion-normal.png (47.31 Kio) Vu 6881 fois
Balise [..] devant votre requête en cours, [R] quand résolu | Pas de message concernant les bots !

Merci

Avatar du membre
jbnh
Modérateur
Modérateur
Messages : 1932
Enregistré le : ven. 02 mai 2008 13:54
Localisation : Bruxelles
Contact :
Status : Hors ligne

Re: [Tuto] Les fonctions récursives

#2

Message par jbnh » ven. 18 juin 2010 00:53

2 - Les vecteurs et diviser pour mieux résoudre

Je suppose que vous connaissez tous ArrayMax, cette fonction qui retourne la valeur maximale d'un tableau. Et bien je vous propose de réécrire cette fonction grâce à des appels récursifs.

Voici un exemple de vecteur informatique, ou array :
Image
La méthode simple :

Le tableau est parcouru et chaque valeur est comparé avec la plus grosse valeur trouvée au préalable.

Code : Tout sélectionner

Const $N = 7

Global $avArray[$N]

$avArray[0] = 5
$avArray[1] = 9
$avArray[2] = 3
$avArray[3] = 6
$avArray[4] = 12
$avArray[5] = 0
$avArray[6] = 2

$resultat = Maximum(0)
msgbox(0,"",$resultat)

Func Maximum($i)
    local $res

    If $i=$N-1 Then
        $res= $avArray[$i] ;Si le tableau ne possède qu'une cellule et donc que N=1 (0= 1-1), alors ce qu'elle contient est forcément le plus grand nombre
                        ;C'est aussi la condition de sortie
    Else    
        $res = Maximum($i+1)        
        If $res < $avArray[$i] Then
            $res=$avArray[$i]
        Endif
    Endif
    return $res
Endfunc
Diviser pour mieux résoudre (ou diviser pour mieux régner) :

On peut également résoudre des problèmes en construisant des algorithmes qui traitent de plus ou moins la moitié des données. C'est diviser pour mieux résoudre. Il n'est pas obligatoire d'utiliser de telles méthodes pour résoudre un problème d'autant plus qu'elles ne sont spécialement plus performantes que les versions triviales. Cependant, l'exemple qui suit est nettement illustratif de cette technique de programmation (diviser pour mieux résoudre).

Code : Tout sélectionner

Local $avArray[7]

$avArray[0] = 5
$avArray[1] = 9
$avArray[2] = 3
$avArray[3] = 6
$avArray[4] = 12
$avArray[5] = 0
$avArray[6] = 2

$resultat = Maximum($avArray,0,6)
msgbox(0,"",$resultat)

Func Maximum($Array,$gauche,$droite)

    Local $m, $u, $v, $res

    If $gauche=$droite Then
        $res= $Array[$gauche]
    Else        
        $m= Floor(($gauche+$droite)/2)      
        $u= Maximum($Array, $gauche, $m)        
        $v= Maximum($Array, $m+1, $droite)  
        
        If $u > $v Then
            $res=$u
        Else
            $res=$v
        Endif        
    Endif
    
    return $res 
Endfunc
On utilise Floor pour avoir un entier car autoit ne distingue pas les déclarations d'entier ou de type float.


BONUS :

Inversion d'une array :

Code : Tout sélectionner

Const $N = 5
Global $avArray[$N]

$avArray[0] = 1
$avArray[1] = 2
$avArray[2] = 3
$avArray[3] = 4
$avArray[4] = 5

For $count = 0 to 4 
    MsgBox(0, "", $avArray[$count])
Next

Miroir(0)

For $count = 0 to 4 
    MsgBox(0, "", $avArray[$count])
Next

Func Miroir($i)

    If $i < Floor($N/2-1) Then
        Miroir($i+1)
    Endif
    
    Local $tmp = $avArray[$N-$i-1]
    $avArray[$N-$i-1] = $avArray[$i] 
    $avArray[$i] = $tmp
    
Endfunc
Balise [..] devant votre requête en cours, [R] quand résolu | Pas de message concernant les bots !

Merci

Avatar du membre
jbnh
Modérateur
Modérateur
Messages : 1932
Enregistré le : ven. 02 mai 2008 13:54
Localisation : Bruxelles
Contact :
Status : Hors ligne

Re: [Tuto] Les fonctions récursives

#3

Message par jbnh » mar. 22 juin 2010 11:56

3 - Le tri rapide (Quicksort)

"Le tri rapide (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes."
Wikipedia.org
Image
Hé oui les amis, qui dit "diviser pour mieux régner" dis fatalement Quicksort. Le quicksort est un algorithme de tri rapide comme son nom l'indique. Le principe est de couper le vecteur à trier en deux sous-vecteurs de taille m et n tel que m+n = taille du vecteur initial. La première étape consiste à mettre dans le premier sous vecteur les m plus petits éléments et dans le second, les n plus grands éléments sans pour autant les trier entre eux. Pour chaque sous-vecteur, on ré-applique la méthode : on les divise en deux vecteurs de taille m et n etc. L'image ci-dessus explicite ce procédé.

Nous devons donc trouver un pivot x dans le vecteur initial pour séparer ce vecteur en deux sous-vecteur et réaliser des appels récursifs pour recommencer la procédure dans ces même sous-vecteurs.

Codons premièrement la fonction Decoupe qui réalisera le partitionnement du vecteur initial en deux sous-vecteurs, et lors des appels récursifs, les sous-vecteurs en sous-sous-vecteurs etc. Rien de bien magique dans cette fonction : elle est extrêmement facile à comprendre :

Code : Tout sélectionner

Func Decoupe(Byref $Array,$gauche,$droite)

 local $pivot=$Array[$droite], $i = $gauche-1
 
    For $j=$gauche to $droite-1 Step 1
    
        If $Array[$j] <= $pivot Then
            $i=$i+1
            $tmp=$Array[$i]
            $Array[$i]=$Array[$j] 
            $Array[$j]=$tmp         
        Endif
    Next
        local $tmp=$Array[$i+1]     
        $Array[$i+1]=$Array[$droite]        
        $Array[$droite]=$tmp ;on place le pivot en bonne position       
        
    return $i+1 ;on retourne la nouvelle position du pivot
Endfunc
On passe bien entendu le vecteur par référence car elle est directement modifiée dans la fonction.

Occupons-nous maintenant de la fonction quicksort qui s'occupe d'appeler Decoupe dans les sous-vecteurs qui nous intéresse :

Code : Tout sélectionner

Global $avArray[7]

$avArray[0] = 5
$avArray[1] = 9
$avArray[2] = 3
$avArray[3] = 6
$avArray[4] = 12
$avArray[5] = 0
$avArray[6] = 2

Quicksort($avArray,0,6)

For $count = 0 to 6
    MsgBox(0, "", $avArray[$count])
Next

Func Quicksort(Byref $Array,$gauche,$droite)

    If $gauche < $droite Then ;condition de sortie
        $p = Decoupe($Array, $gauche, $droite)
        Quicksort($Array, $gauche, $p-1)
        Quicksort($Array, $p+1, $droite)
    Endif
Endfunc
Alors, blague à part, plutôt facile non ? On vient de coder _ArraySort, la preuve :
_ArraySort
Sort a 1D or 2D array on a specific index using the quicksort/insertionsort algorithms.
Bien entendu, plein de Quicksort existent, notamment le Quicksort avec boucle n+1/2, avec jeux sur pointeurs, ou même avec seulement un paramètre !
Balise [..] devant votre requête en cours, [R] quand résolu | Pas de message concernant les bots !

Merci

Avatar du membre
timmalos
Modérateur
Modérateur
Messages : 1970
Enregistré le : dim. 18 mai 2008 14:16
Contact :
Status : Hors ligne

Re: [Tuto] Les fonctions récursives

#4

Message par timmalos » mar. 22 juin 2010 12:45

Regroupement des messages
► Afficher le textePremier message timmalos
► Afficher le textereponse de ZDS

Avatar du membre
jbnh
Modérateur
Modérateur
Messages : 1932
Enregistré le : ven. 02 mai 2008 13:54
Localisation : Bruxelles
Contact :
Status : Hors ligne

Re: [Tuto] Les fonctions récursives

#5

Message par jbnh » jeu. 24 juin 2010 10:37

4 - Le Backtracking

Définition : Le backtracking permet de trouver une solution à un problème en essayant plusieurs possibilités. Si un chemin emprunté semble erronée ou mener à une solution incorrecte, l'algorithme revient en arrière, repart à l'endroit il a fait le mauvais choix et teste une autre voie.

Génération exhaustive :

On distingue également la génération exhaustive, c'est-à-dire que dans ce procédé, on énumère toutes les structures d'un ensemble donné. Par exemple, si on veut générer tout les mots de 5 lettres donné par notre alphabet, sans backtracking on s'y prendrait ainsi :

Code : Tout sélectionner

$text = ""
For $char = 97 to 122
$text &= Chr($char)
    
    For $char = 97 to 122
    $text &= Chr($char)
    
        For $char = 97 to 122
        $text &= Chr($char)
        
        ....
            msgbox(0,"",$text) ;afficher le premier mot
            $text = "" ;réinitialiser texte
        
        Next
    Next    
Next   
Imaginez si l'ont devait afficher tous les mots de 100 lettres !

Mais avec le backtracking, regardez bien :

Code : Tout sélectionner

const $N = 2 ;longueur du mot, prenons 2 pour pas trop faire ramer le pc ^^
Dim $array[$N]
Global $mots

GenerationMot(0)

msgbox (0,'',$mots)

Func GenerationMot($i)

    If $i=$N Then ;FIN -> AFFICHAGE AVEC LE BACKTRACKING
        
        For $j=0 to $N-1 step 1
            $mots &= $array[$j]
        Next
        $mots &= " "
        
    Else
        For $char = 97 to 122
            $array[$i] = Chr($char)
            GenerationMot($i+1)
        Next        
    Endif

Endfunc
En clair, au début on met dans array[0] "a" -> i+1 array[1] "a" -> i+1 ... -> i = n backtracking -> array[n-1] = "b" -> i = n backtracking -> array[n-1] = "c" etc

D'ou l'exemple avec deux lettres donne bien :

aa ab ac ad .... az ba bb bc.....
Démolition d'une solution
Contrairement à la définition donnée en début de post, la génération exhaustive ne cherche pas spécialement une bonne solution, elle génère toutes les possibilités d'un ensemble donné. Si dans un problème, seulement quelques solutions nous conviennent, il faut tester toutes les possibilités, certes, mais éliminer celle qui ne répondent pas au problème et non les énumérer comme la génération exhaustive. Nous devons donc démolir des solutions partielles.

Prenons l'exemple d'un sac dont on définit le volume au préalable. Nous avons plusieurs briques de volume différent à disposition. Le but est de rechercher toutes les combinaisons telles que le volume des briques dans le sac = le volume total du sac. Par exemple si le sac a un volume de 10 et qu'on a mis des briques dont le total vaut 9. Si il nous reste une brique de volume 2, 4 et 7, on va dépasser 10 donc la combinaison essayée est fausse.

Regardez plutôt ce script :

Code : Tout sélectionner

;le nombre d'objets, disons des briques, à notre disposition
Global $n = InputBox("Question", "Nombre d'objets ?", "10")

Dim $volume[$n]
Dim $bool[$n]
Global $volumesac
Global $volumetotal

;définition du volume des objets, prenons ici objet1 à un volume 1, objet 2 volume de 2 etc.
For $j=0 To $n-1 Step 1
    $volume[$j]=$j+1
Next

;Le sac peut contenir au maximum des briques dont le volume total vaut 10
$volumetotal = InputBox("Question", "Volume du sac ?", "10")

Combinaisons(0)

Func Combinaisons($i)

    If $i = $n Then ;si on est à la fin d'une possibilité
        If $volumesac = $volumetotal Then ;si elle est juste
        local $texte
            For $j=0 to $N-1 step 1 ;on affiche
                If $bool[$j] = true Then
                    $texte &= $volume[$j]&"+"
                Endif
            Next
            $texte &= "="&$volumetotal
            msgbox(0,"",$texte)
        Endif
    Else
        ;premier essai, on prend l'objet $i
        $bool[$i] = true
        $volumesac += $volume[$i]
        Combinaisons($i+1)
        ;démolition de la solution partielle
        $volumesac -= $volume[$i]
        
        ;deuxieme essai, on ne prend pas l'objet $i
        $bool[$i] = false
        Combinaisons($i+1)
        ;Fin du script donc pas nécessaire de détruire la solution partielle  
    Endif
Endfunc
Il correspond parfaitement à notre attente. En clair toutes les combinaisons seront testées grace aux booléens. Un peu à l'instar des mots (script précédent), on teste toutes les possibilités :
true, true ,true, true
true, true ,true, false
true, true, false, true
true, true, false, false
...

A la fin de chaque combinaison, si le volume des briques choisies est égal au volume du sac : c'est gagné on affiche la solution. Si on dépasse, on détruit la solution grâce à $volumesac -= $volume[$i].
Cet exemple est bien entendu plutôt facile, mais si vous aimez il y a bien plus dur ! Orientez vous par exemple vers le problème des huit dames ou le voyageur de commerce résolu grâce à l'algorithme branch & bound.

Ceci clôt ce tutorial. N'hésitez pas si vous avez des questions.
Balise [..] devant votre requête en cours, [R] quand résolu | Pas de message concernant les bots !

Merci

Répondre