Cours Visual Basic .NET récursivité

Site

Cours VB.net

1.15

Récursivité.

La récursivité c'est quoi?

Définition:

Exemple trouvé sur developpeur.journaldunet.com :

"C'est l'histoire d'un petit garçon qui ne voulait pas dormir et dont la mère lui raconte l'histoire de la petite grenouille qui ne voulait pas dormir et dont la mère lui raconte l'histoire de l'ourson qui ne voulait pas dormir et dont la mère lui raconte l'histoire du bébé écureuil qui s'est endormi, et l'ourson s'endormi, et la petite grenouille s'endormi, et le petit garçon s'endormi."

Cette histoire, permet de mieux voir ce qui se produit lors de la récursivité: la procédure (le petit qui ne dort pas et à qui on raconte une histoire) appelle, la même procédure (le petit qui ne dort pas et à qui on raconte une histoire) qui appelle la même procédure..... on passe au "niveau" suivant puis au suivant tant qu'on n'a pas atteint la condition d'arrêt (ici, l'endormissement). Celle-ci atteinte, la récursion se termine pour les autres niveaux en sens inverse en remontant.

Une procédure est récursive si elle peut s'appeler elle même.

VB accepte les procédures récursives:

Sub Calcul()

Calcul()

End Sub

On voit ici que la procédure Calcul() s'appelle elle même: la ligne centrale appelle de nouveau la procédure Calcul() avec nouveaux paramètres, nouvelles variables locales, à la sortie de la procédure (après End Sub), retour à la 'version' précédente de la procédure Calcul() ou on retrouve les variables de la précédente version.

Une procédure non récursive appelle, elle, d'autres procédures.

Pourquoi utiliser la récursivité?

Une procédure récursive découpe le problème en morceaux plus petits et s'appelle elle même pour résoudre chacun des plus petits morceaux, elle résout une petite partie du problème elle même.

Sub Calcul(Gros)

If..

Résout petit problème

Else

Découpe

Calcul(Petit)

End If

End Sub

Ici 'Résout petit problème' s'appelle le point terminal ou le point d'arrêt, c'est la branche d'une condition qui n'appelle pas de nouveau la fonction Calcul(). C'est indispensable.

Si on n'est pas dans le cas du point d'arrêt, la procédure découpe le problème en plus petit morceaux et pour chaque morceau on appelle de nouveau le procédure:

Sub Calcul(Gros)

If..

Découpe

Calcul(Petit)

End If

End Sub

A un moment donné, la condition n'est pas remplie, cela correspond au point terminal.

On se rend compte qu'une bouche For Next peut être transformée en procédure récursive:

Exemple :

Créons une procédure qui ajoute N éléments par ordre décroissant (ajoute l'élément N puis N-1 puis ... 2 puis 1)

On l'appelle avec Calcul(10) par exemple:

Avec For:

Function Calcul(N As Integer)

Dim total As Integer

For i= N to 1 Step-1

total=total + i

Next i

Calcul=total

End Function

Avec la récursivité:

Function Calcul(N As Integer)

Dim total As Integer

If N>0 Then

total= N+ Calcul (N-1)

End If

Calcul= total

End Fonction

On l'appelle avec Calcul(10)

Mais la récursivité ne sert pas seulement à cela, elle sert à résoudre aussi des problèmes qui seraient extrêmement complexes en programmation non récursive.

Règles fondamentales d'une fonction récursive:

1-La récursivité doit s'arrêter à un moment donné.

Il doit y avoir un point terminal (ou point d'arrêt)

Il doit y avoir dans la fonction récursive, une expression conditionnelle dont au moins un des cas conduit à une expression évaluable.

Il doit donc y avoir un chemin non récursif (chemin ou la fonction ne s'appelle pas de nouveau).

Il doit y avoir un test qui survient obligatoirement et qui arrête le fonctionnement récursif sinon la fonction tourne sans fin (ou du moins, elle plante quand la pile est pleine).

Dans notre exemple 1, quand n=1 la récursivité s'arrête.

Dans notre exemple 2, quand il n'y a plus de parenthèse, on n'appelle plus la fonction Calcul, on fait le calcul simple et on sort de la fonction ce qui la fait 'remonter'.

2- A aucun moment les paramètres appelant de nouveau la fonction doivent être les mêmes que l'appel précédent.

Sinon cela tournera indéfiniment.

3-Le nombre d'appel récursif ne doit pas être très grand.

Sous peine de 'StackOverflow': la pile des appels qui stocke les adresses de retour de chaque appel récursif est pleine, elle dépassent ses capacités.

Certains ajoute dans le code de la fonction récursive 'un compteur de sécurité':

Sub Calcul(ByRef Compteur As Long)

If Compteur> LIMITE Then Exit Sub

Compteur= Compteur+1

Calcul(Compteur)

End Sub

Noter que le compteur est un paramètre ByRef, ce qui permet de toujours incrémenter la même variable.

Voir exemple sur les fractales.

4-La fonction récursive ne doit pas déclarer un grand nombre de variables ou d'objets.

Sous peine d'occuper une place trop importante en mémoire.

5-Limiter les fonctions récursives à une seule procédure, éviter plusieurs fonctions récursives imbriquées.

Sinon cela devient vite trop complexe.

6- Chaque fois qu'elle est appelée de manière récursive (par elle-même, donc), un ou plusieurs des arguments qui lui sont transmis doivent se rapprocher de la condition d'arrêt.

Sinon il n'y aura pas d'arrêt.

7- La complexité du problème doit être réduite à chaque nouvel appel récursif.

8- Ne peut -on pas faire plus simple avec une boucle For Next?

Parfois une boucle simple remplace avantageusement une fonction récursive. Dans ce cas utiliser la boucle!!

C'est le cas de la fonction factorielle!!

Exemple 0: Inversion de chaîne

Soit une chaîne de caractères, on veut une fonction qui inverse cette chaîne: dernier caractère en premier, avant dernier en second...

Exemple: "abcd" retournera "dcba"

Principe de la fonction 'inverse' récursive:

La fonction 'inverse' met le dernier caractère au début et appelle la fonction 'inverse' avec comme paramètre la chaîne moins le dernier caractère.

Exemple "abcd", on met "d" au début et rappelle la fonction inverse avec comme paramètre "abc"

Point d'arrêt: si la chaîne est vide on retourne une chaîne vide.

Function inverse(ByVal st As String) As String

If st = "" Then

inverse = ""

Else

inverse = st.Substring(st.Length() - 1, 1) + inverse(st.Substring(0, st.Length() - 1))

End If

End Function

Exemple 1: calcul de 'Factorielle'.

On rappelle que N! (factorielle N)= 1*2*3*...*(N-2)*(N-1)*N

Exemple Factorielle 3 =1*2*3

Dim R As Long

R=Factorielle(3) 'retournera 6

Cette fonction n'est pas fournie par VB, créons une fonction Factorielle SANS récursivité:

Function Factorielle (ByVal N as Long) As Long

Dim i As Long

Resultat=1

For i= 1 to N

Resultat=i* Resultat

Next i

Return Resultat

end Function

Cela crée une fonction recevant le paramètre N et retournant un long.

La boucle effectue bien 1*2*3...*N-1*N.

Factorielle avec 'Récursivité':

Une autre manière de calculer une factorielle est d'utiliser la récursivité.

Comment faire?

On sait que N!= N * (N-1) * (N-2).... 3 * 2 * 1

on remarque donc que Factorielle N!= N * Factorielle(N-1)

N!= N*(N-1)! : en sachant que 1!=1

Créons la fonction:

Si N=1 la fonction retourne 1 sinon elle retourne N* factorielle(N-1)

Function Factorielle (ByVal N as Long) As Long

If N=1 then

Return 1

Else

Return N* Factorielle(N-1)

End If

end Function

Dans la fonction Factorielle on appelle la fonction Factorielle, c'est bien récursif.

Pour N=4:

La fonction 'descend' et appelle chaque fois la factorielle du nombre inférieur.

La fonction Factorielle est appelée 4 fois :

Factorielle (4) appelle Factorielle(3) qui appelle Factorielle(2) qui appelle Factorielle (1)

Puis la fonction remonte en retournant le résultat de chaque factorielle.

Factorielle (1) retourne 1

Factorielle (2)retourne 2 '2*factorielle(1)

Factorielle (3)retourne 6 '3*factorielle(2)

Factorielle (4) retourne 24 '4*factorielle(3)

Vb gère cela avec une pile des appels. il met dans une pile les uns aux dessus des autres les appels, quand il remonte, il dépile de haut en bas (Dernier rentré, premier sortie)

Attention: La pile a une taille maximum, si N est trop grand, on déclenche une erreur de type StackOverflow.

Exemple 2: calcul d'une expression avec parenthèses multiples:

Comment calculer la valeur de la chaîne "(4+2(2*8)-(5/(8+1)))"

Une partie du code nommée Calculsimple sait calculer une chaîne de type "8+1" ou "4+2" sans parenthèses.

Il faut gérer les parenthèses,: la sub découpe ce qui est entre parenthèse et s'appelle elle même pour calculer ce qui est entre parenthèses:

La sub calcul fait 2 choses:

Si il y a des parenthèses: appelle Calcul() avec comme paramètre la chaîne entre parenthèse puis remplace la chaîne entre parenthèse par sa valeur

Si il n'y a pas de parenthèses calcule l'expression simple (= - * /).

Sub Calcul(Chaine As String) As String

Si Chaine contient "("

Decouper ValeurEntreParenthese

Resultat=Calcul (ValeurEntreParenthese) 'Appel récursif

Remplacer (ValeurEntreParenthese) par Resultat

Sinon

CalculSimple

Fin Si

End Sub

Exemple 3: PGCD

On rappelle que le PGCD est le 'Plus Grand Commun Diviseur'.

Soit a et b 2 nombres.

Si b divise a => PGCD=b. sinon, PGCD(a,b) = PGCD(b, a mod b)

Function PGCD(ByVal P As Long, ByVal Q As Long) As Long

If Q Mod P = 0 Then

Return P

Else

Return PGCD(Q, P Mod Q)

End If

Exemple 4: Tri récursif:

Tri récursif

Le principe est que la fonction récursive scinde le tableau en 2 et pour chaque partie appelle de nouveau le tri récursif, la condition d'arrêt survient quand le dernier élément est < ou = au premier.

Dans un premier temps on range le tableau de telle sorte que tous les éléments inférieurs à l'élément d'indice pivot se trouvent placés à la gauche de celui-ci et donc tous les éléments supérieurs à sa droite.Ensuite on appelle à nouveau (récursivement) la procédure QuickSort pour chacun des deux sous-tableaux.

Cette méthode de tri récursif qui se nomme QuickSort est proportionnellement efficace au désordre du tableau à trier. Cette méthode mettra plus de temps (qu'une autre méthode) à trier un tableau qui est déjà en parti trié qu'un tableau rangé au hasard... Mais en cas de désordre intégral, c'est certainement la plus rapide.

Sub QuickSort(debut As Integer, fin As Integer)
Dim pivot, gauche, droite, temp  As Integer

  pivot  = debut
  gauche = debut
  droite = fin
  do
    if t(gauche) >= t(droite) then
    'échanger si nécessairet(droite) et t(gauche)
      temp = t(gauche)
      t(gauche) = t(droite)
      t(droite) = temp
      pivot = gauche + droite - pivot 'nouvelle position du pivot
                     'pivot est alors égal à droite ou à gauche car pivot était avant égal
                     'à gauche ou à droite
    End If
    if pivot = gauche then droite=droite-1 else gauche=gauche+1
  loop until gauche = droite
  if debut < gauche - 1 then QuickSort(debut, gauche - 1) ' //appel récursif sur la partie gauche
  if fin > droite + 1 then QuickSort(droite + 1, fin)  'appel récursif sur la partie droite

End Sub

Comment l'utiliser:

On crée un tableau Public d'integer contenant les valeurs à trier:

Public t() As Integer = {10, 2, 7, 4, 1, 3, 12, 6}

Dim i As Integer

Call QuickSort(0, 7) 'paramètre= premier et dernier élément du tableau

Affichage du tableau trié dans une texteBox1

For I = 0 To 7

TextBox1.Text = TextBox1.Text + ControlChars.CrLf + t(i).tostring

Next

Exemple 5: Parcours de répertoires et sous répertoires:

On veut afficher dans une ListBox les noms des répertoires, sous-répertoires et fichiers:

On crée une routine AfficheTree qui affiche

Le nom du répertoire courant.

Le nom des fichiers du répertoire courant.

Qui parcourt les sous-répertoires et pour chacun d'eux appelle AfficheTree

Imports System.IO

Sub AfficheTree ( ByVal myDir As String, ByVal Optional Niveau As Integer =0)

'Affiche le répertoire myDir

List1.Items.Add(New String (" ", niveau *2) & myDir)

'Affiche les fichiers

For Each fichier As String In Directory.GetFiles( myDir)

List1.Items.Add(New String (" ", niveau *2+2) & fichier)

'Parcourt les sous-répertoires

For each sousRepertoire As String In Directory.GetDirectories( myDir)

'Appel de manière récursive 'AfficheTree pour afficher le contenu des sous répertoires.

AfficheTree (sousRepertoire, niveau+1)

End Sub

Exemple 6: Évaluation d'un nombre écrit en chiffre romain:

On veut taper III et voir s'afficher 3

taper M et voir s'afficher 1000

taper XLVIII et voir s'afficher 48

On remarque (je l'ai pas fait tout seul!!) que:

Pour un caractère romain, il a une valeur (I=1, V=5, X=10, L=50, C=100, D=500, M=1000)

Pour deux caractères, on compare leurs valeurs:

Si le premier est plus petit, on le soustrait au second: IX = 10 - 1 = 9

Si le premier est plus grand, on l'ajoute au second: VI = 5 + 1 = 6

Pour une suite de n caractères: en partant de la gauche, si le premier chiffre a une valeur inférieure au deuxième, alors on le soustrait de la valeur de tout le reste, sinon on l'additionne à la valeur de tout le reste..

Le programme va donc comparer la valeur des 2 caractères de gauche; il va ajouter (si la valeur du premier est plus grande) ou soustraire (si la valeur du premier est plus petite) la valeur du premier caractère à la valeur de la chaîne raccourcie du premier caractère.

Exemple: pour XLVIII

X plus petit que L donc -10 +valeur de (LVIII)

L plus grand que V donc -10 +50 + valeur de (VIII)

V plus grand que I donc -10 +50 + 5 + valeur de (III)

...

Il faut créer un routine nommée valeur qui calcule la valeur d'un caractère.

Et la routine Eval qui calcule l'expression

S'il y a un caractère dans la chaîne c passée en paramètre, on retourne sa valeur, s'il y en a plusieurs, on compare les 2 premiers caractères, et on additionne ou soustrait à la valeur du premier caractère l' Eval (appel récursif) du reste de la chaîne.

Function valeur(ByVal c As Char) As Integer

Select Case c

Case "M"c : valeur = 1000

Case "D"c : valeur = 500

Case "C"c : valeur = 100

Case "L"c : valeur = 50

Case "X"c : valeur = 10

Case "V"c : valeur = 5

Case "I"c : valeur = 1

End Select

End Function

Function eval(ByVal s As String) As Integer

Dim n As Integer

If s.Length = 1 Then

eval = valeur(s.Chars(0))

Else

n = valeur(s.Chars(0))

If n < valeur(s.Chars(1)) Then n = -n

eval = n + eval(s.Substring(1, s.Length - 1))

End If

End Function

Si on veut tester: créer dans une form 2 texteBox: TextDecimal, TextRomain et un bouton Button1

Private Sub Button1_Click

TextDecimal.Text = eval(TextRomain.Text).ToString

End Sub

Exemple 7: Suite de Fibonacci

« Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? »

On suppose que :

le premier mois, il y a juste une paire de lapins ;
les lapins ne sont pubères qu'à partir du deuxième mois ;
chaque mois, toute paire susceptible de procréer engendre effectivement une nouvelle paire de lapins ;
les lapins ne meurent jamais (donc la suite de Fibonacci est strictement croissante).

Sont notés en rouge, les couples productifs.

En janvier : 1 couple
En février : 1 couple
En mars : 1 + 1 = 2 couples
En avril : 1 + 2 = 3 couples
En mai : 2 + 3 = 5 couples
En juin : 3 + 5 = 8 couples
En juillet : 5 + 8 = 13 couples
En août : 8 + 13 = 21 couples
En septembre : 13 + 21 = 34 couples
En octobre : 21 + 34 = 55 couples
En novembre : 34 + 55 = 89 couples
En décembre : 55 + 89 = 144 couples

Les réponses constituent les nombres de la suite de Fibonacci : 1 - 1 - 2 - 3 - 5 - 8 - 13 - 21 - ..., dont chaque terme à partir du 3ème est la somme des deux précédents.

Function Fibonacci(ByVal n As Integer)

' si n > 91, cela entraîne un overflows sur les long.

Dim result As Long = 0

If n < = 2 Then

result = 1

Else

result = Fibonacci(n - 1) + Fibonacci(n - 2)

End If

Return result

End Function

Programme itératif correspondant:

Function Fibonacci2(ByVal n As Integer)

Dim u, v, w, i As Long

If n <= 0 Then Return 0

If n = 0 Then Return 1

u = 0

v = 1

For i = 2 To n

w = u + v

u = v

v = w

Return v

End Function

Exemple 8: Fractales

Calculs de fractales

Les fonctions fractales sont des fonctions récursives théoriquement infinies...

Le Flocon de Koch, du nom du mathématicien suédois Helge Von Koch (1870-1924), est une courbe fermée, reproduisant un triangle équilatéral à des échelles de plus en plus petites. En répétant ce processus une infinité de fois, la courbe obtenue possède alors un périmètre infini mais une aire limitée. Pour ce faire, chaque segment formant un triangle équilatéral est lui-même décomposé en un triangle équilatéral dont la base mesure un tiers du segment, centrée et confondue à ce segment.

On va donc créer une fonction récursive nommée 'flocon' qui décompose un segment en ajoutant un triangle puis qui pour chaque segment appelle la fonction 'flocon.

Comme on ne peut pas afficher des points infiniment petits, on va ajouter une condition d'arrêt qui est déclenchée par le nombre d'appel récursif. Si la condition d'arrêt est remplie, on dessine le segment.

Voici la fonction récursive:

Private Sub Flocon(ByRef gh As Graphics, ByVal a As Point, ByRef b As Point, ByRef n As Integer)

'procédure récursive pour dessiner la fractale de Von Koch

Dim d, c, e As Point

Dim Couleur As Color = Color.Aqua

If n = 0 Then

'Condition de sortie de la récursivité

gh.DrawLine(New Pen(Color.Red), a.X, a.Y, b.X, b.Y)

Else

'Appel récursif

c = Tiers(a, b)

d = Tiers(b, a)

e = Sommet(c, d)

Flocon(gh, a, c, n - 1)

Flocon(gh, c, e, n - 1)

Flocon(gh, e, d, n - 1)

Flocon(gh, d, b, n - 1)

End If

End Sub

Pour que cela fonctionne, il faut les trois routines suivantes:

Private Function Sommet(ByRef a As Point, ByRef b As Point) As Point

'Calcule le sommet du triangle équilatéral

'dont la base est définie par 2 points

Sommet.x = (b.x + a.x) / 2 + (b.y - a.y) * Racine3Sur2

Sommet.y = (b.y + a.y) / 2 - (b.x - a.x) * Racine3Sur2

End Function

Private Function Milieu(ByRef a As Point, ByRef b As Point) As Point

'Calcule le milieu d'un segment

Milieu.x = (b.x + a.x) / 2

Milieu.y = (b.y + a.y) / 2

End Function

Private Function Tiers(ByRef a As Point, ByRef b As Point) As Point

'Calcul le premier tiers d'un segment

'Attention: Le résultat est orienté

Tiers.x = (b.x - a.x) / 3 + a.x

Tiers.y = (b.y - a.y) / 3 + a.y

End Function

Pour utiliser cet exemple il faut dans un formulaire un PictureBox nommé PictureBox1 pour afficher la fractale, un TextBox1 permettant de saisir le nombre d'appel récursif( ne pas dépasser 9 en pratique), et un bouton command1 exécutant le calcul et l'affichage.

Mettre en haut du module:

Const Racine3Sur2 As Double = 0.866025404

Private Sub Command1_Click(ByVal eventSender As System.Object, ByVal eventArgs As System.EventArgs) Handles Command1.Click

Dim newBitmap As Bitmap = New Bitmap(400, 400)    'créons un BitMap

Dim g As Graphics = Graphics.FromImage(newBitmap) 'créons un Graphics et y mettre le BitMap

Dim t As Integer

'déclarons les 3 points du triangle initial

Dim a(2) As Point

Dim b(2) As Point

'donnons une valeur à 2 points, calculons le troisième

a(0).X = 164

a(0).Y = 10

b(1).X = 20

b(1).Y = 260

b(0) = Sommet(a(0), b(1))

a(1) = b(0)

a(2) = b(1)

b(2) = a(0)

'Pour chaque coté

For t = 0 To 2

'Appelons la fonction récursive

    Flocon(g, a(t), b(t), Val(Text1.Text))

Next t

'Affichons

PictureBox1.Image = newBitmap

End Sub

Code issu d'un code VB6 situé sur CodeS-SourceS VBFrance.com écrit par D. Thuler et transcrit par moi en VB.Net.Merci David.

Autres exemples:

Recherche de chemin dans un labyrinthe.

Le principe est que la fonction récursive teste le déplacement à droite, à gauche, en haut, en bas. La condition d'arrêt se produit quand on a trouvé la sortie; les endroits ou on est déjà passé sont notés.

L'article http://recursivite.developpez.com/ donne des exemples et des explications extraordinaires de programme récursifs EN PASCAL. Si vous avez le courage de les traduire en VB , envoyez les moi!!

Exemple trouvé sur developpeur.journaldunet.com