Procédure Récursive

[Shadow]

Salut,

Je ne comprends pas comment fonctionne les Procédure Récursive
Moi je pensais que c'était une procédure qui s'appel et créer une autre procédure comme si c'était une procédure dans une procédure dans une procédure etc...

Ou alors c'est juste le code qui est répliqué ?

Ici je pensais que la procédure serais appelé 10 fois ou 100 mais je ne dois pas avoir calculé, peut être que c'est 10 ^ 10 fois ?
Je pensais que chaque variable était indépendante de la procédure, donc chaque nouvel appel à la procédure créer d'autres variable et non pas les mêmes...

Code : Tout sélectionner

Procedure Recursif()
  
  For I = 1 To 10
    Debug I
    Delay(1000)
    Recursif()
  Next
  
EndProcedure

Recursif()

Qui pourrait m’expliquer comment ça fonctionne svp ?

[falsam]

ou comme ça

Code : Tout sélectionner

Procedure Recursif()
  Static i
  
  If i < 10
    Debug I
    Delay(1000)
    i + 1
    Recursif()
  EndIf
EndProcedure

Recursif()

[falsam]

Parcourir un dossier et ses sous dossiers

Code : Tout sélectionner

Procedure.s ParseDirectory(folder.s, id.l = 0)
  
  If Right(folder, 1) <> "\"
    folder + "\"
  EndIf
  
  If ExamineDirectory(id, folder, "*.*")
    
    While NextDirectoryEntry(id)
      
      If DirectoryEntryName(id) <> "." And DirectoryEntryName(id) <> ".."
               
        Debug folder + DirectoryEntryName(id)
                
        If DirectoryEntryType(id) = #PB_DirectoryEntry_Directory
          ParseDirectory(folder + DirectoryEntryName(id), id + 1)
        EndIf
        
      EndIf
      
    Wend
    
    FinishDirectory(id)
    
  EndIf
  
EndProcedure 

ParseDirectory("c:\windows")

[Ollivier]

Une procédure récursive est un maillon de développement.

La récursivité est une opération de pénétration dans un domaine aux caractéristiques non mesurées. Ça peut être une zone graphique, une table d'allocation de fichiers, etc...

L'opération de récursivité ne doit pas être infinie : il faut la limiter, par les moyens dépendamment de ce qu'il y a à pénétrer.

Code : Tout sélectionner

Procedure UneProc(x.I)
   If x
      Debug "Avancée " + Str(x)
      UneProc(x - 1)
      Debug "Repli " + Str(x)
   EndIf
EndProcedure

UneProc(3)

[PAPIPP]

Bonjour à tous

Voici un exemple simple

La résolution de la factorielle peut être réalisée par 2 procédures l’une itérative et l’autre récursive .

Sachant que fact(n)=fact(n-1)*n on voit apparaitre la récursivité

Code : Tout sélectionner

Procedure.q fact_ite(n)
fact.q=1
For i=1 To n
fact*i
Next
ProcedureReturn fact
EndProcedure

Debug "fact_ite="+Str(fact_ite(10))

Procedure.q fact_rec(n)
Define factr.q=1
If n>1
factr*fact_rec(n-1)*n
EndIf
ProcedureReturn factr
EndProcedure
Debug "fact_rec="+Str(fact_rec(10))

A+

[Shadow]

Bonsoir, merci de vos exemple mais cela ne m'aide pas du tout !
J'ai besoin d'info sur comment fonctionne la récursivité d'une procédure.

Dites-moi, qu'est ce que la récursivité ?
Comment ça marche ?

Concrètement ça fais quoi ?
Voir mon message.

Les variables, comment ça marche dans ces cas là ?
Moi je croyais que ça marchait comme ça en gros:!

Est ce que ce code:

Code : Tout sélectionner

Procedure MaProcedure()
  
  A + 1 ; A (01) ici vaudra 1, 2
  Delay(100)
  
  If A < 3
    MaProcedure()
  EndIf
  
EndProcedure

Est égale à ce code ?:

Code : Tout sélectionner

Procedure MaProcedure()
  
  A + 1 ; A (01) ici vaudra 1, 2
  Delay(100)
  
  If A < 3
    
    Procedure MaProcedure()
      
      A + 1 ; A (02) ici vaudra 1, 2
      Delay(100)
      
      If A < 3
        
        Procedure MaProcedure()
          
          A + 1 ; A (03) ici vaudra 1, 2
          Delay(100)
          
          If A < 3
            
            Procedure MaProcedure()
              
              A + 1 ; A (04) ici vaudra 1, 2
              Delay(100)
              
              If A < 3
                
                Procedure MaProcedure()
                  
                  A + 1 ; A (05) ici vaudra 1, 2
                  Delay(100)
                  
                  If A < 3
                    ; Etc.
                  EndIf
                  
                EndProcedure
                
              EndIf
              
            EndProcedure
            
          EndIf
          
        EndProcedure
        
      EndIf
      
    EndProcedure
    
  EndIf
  
EndProcedure

En procèdent comme ceci, effectivement il y à boucle infinie...
Ce qui m’intéresse de savoir, est ce que chaque variable est bien indépendante ?

Chaque récursivité à bien ces propres variables et ne sont pas mélanger avec les autres ok ?
Donc avec ce code, j’obtiens une infinité de variable 'A' mais locale à chaque récursivité c'est bien ça ?

Code : Tout sélectionner

Procedure MaProcedure()
  
  A + 1 ; A (01) ici vaudra 1, 2
  Delay(100)
  
  If A < 3
    MaProcedure()
  EndIf
  
EndProcedure

[Demivec]

Plus achevé:

Code : Tout sélectionner

Procedure MaProcedure(A = 0)
  
  Debug "Valeur de départ A =  " + A
    
  If A >= 3
    ;Cas de base, n'utilise plus de récursivité.
    Debug "Case de base A = " + A
    ProcedureReturn
  Else
    ;Un ensemble de règles qui réduit tous les autres cas au cas de base.
    MaProcedure(A + 1)
  EndIf
    
  Debug "Valeur finale A = " + A
EndProcedure

MaProcedure()
Debug "----------------"
MaProcedure(-2)
Debug "----------------"
MaProcedure(5)

Chacune de ces variables est assez indépendante (paramètres, Define, Protected) mais pas celles-ci (Global, Static).

[PAPIPP]

Bonjour Shadow
Pour voir comment évolue la ou les variables dans une procédure récursive utilise le mode débug en pas à pas.

Voici un exemple qui permet de vérifier l'indépendance des 2 variables factre= et factre*

Code : Tout sélectionner

Procedure.q fact_rec(n)
Define  factre.q=1
If n>1
factre=fact_rec(n-1)*n  ;;; on peut remplacer factre=fact_rec(n-1)*n  par factre*fact_rec(n-1)*n ce qui ne change rien au résultat
EndIf
ProcedureReturn factre
EndProcedure
Debug "fact_re="+Str(fact_rec(10))

A+

[falsam]

Bonsoir, merci de vos exemple mais cela ne m'aide pas du tout !

Un souci pour les comprendre ?

Je vais te donner une explication le plus simple possible qui va détruire l'espoir que tu avais dans ces procédures récursives.

Chaque récursivité à bien ces propres variables et ne sont pas mélanger avec les autres ok ? ... j’obtiens une infinité de variable 'A' mais locale à chaque récursivité c'est bien ça ?

Suspens ....... ET BIEN NON Ha Ha Ha terminé les espoir que tu avais dans cette façon de faire



Une procédure récursive n'ira pas créer plusieurs autres procédures avec chacune ses variables indépendantes comme tu le montres dans ton exemple.

Une procédure récursive est une procédure qui s'appelle elle même à l'intérieur de sa procédure avec un certain nombre d'itérations.

Un petit exemple (Oui un de plus ^^)

Code : Tout sélectionner

Procedure MethodeCoue()
  Static RepeteDixFois
  
  RepeteDixFois + 1
  Debug "j'ai confiance en moi " + Str(RepeteDixFois) + " fois"
  
  ; On se le répéte 10 fois
  If RepeteDixFois < 10
    MethodeCoue()
  EndIf
EndProcedure

MethodeCoue()

Debug #CRLF$ + "HaaaaAAAAaaaa, ca va mieux !"

Mon exemple est moisi car sans intéret.

Je pense que le bonheur est dans le Thread ..... A suivre

[Marc56]

Mon exemple est moisi car sans intéret.

Pas du tout, il irait même très bien avec les autres exemples dans la doc officielle pour illustrer les procédure récursives
https://www.purebasic.com/french/docume ... dures.html

[Mindphazer]

Mon exemple est moisi car sans intéret.

Nan moi il me plaît bien
Comme le dit Marc, il devrait être intégré à la doc

[microdevweb]

Je ne sais pas si cela pourra t'aider, voici un petit exemple avec la possibilité d'ajouter des procédures personnalisées

Code : Tout sélectionner

Prototype proc(*cat)
Structure cat
  nom.s      ; nom de la catégorie
  parent.l   ; indice du parent
  maPro.proc ; une procédure personalisée
EndStructure
Global NewMap mesCat.cat() ; liste de toutes les catégories

; procédures personalisée
Procedure pr1(*el.cat)
  Debug "procédure_1 pour "+*el\nom
EndProcedure

Procedure pr2(*el.cat)
  Debug "procédure_2 pour "+*el\nom
EndProcedure


; exemple ajout de 100 catégories 
For i = 1 To 100
  AddMapElement(mesCat(),Str(i))
  With  mesCat()
    \nom = "cat_"+Str(i)
  EndWith
Next

; je vais placer quelques parent au hasard
For i = 1 To 100
  With  mesCat()
    ; un petit random pour ajouter ou non un parent 
    ; 1 j'ajoute 0 je n'ajoute pas
    If Random(1,0)
      If FindMapElement(mesCat(),Str(i))
        \parent = Random(100,1)
      EndIf
    EndIf
    ; un petit random pour ajouter ou non une procédure
    ; 1 j'ajoute 0 je n'ajoute pas
    If Random(1,0)
      If FindMapElement(mesCat(),Str(i))
        ; et choix de la procédure au hazard
        If Random(1,0)
          \maPro = @pr1()
        Else
          \maPro = @pr2()
        EndIf
      EndIf
    EndIf
  EndWith
Next

; procédure récursive trouve parent
Procedure chercheParent(*cat.cat)
  If FindMapElement(mesCat(),Str(*cat\parent))
    Debug *cat\nom+" est parent de "+mesCat()\nom
    chercheParent(@mesCat()) ; je me rappelle moi même
  EndIf
  ProcedureReturn 
EndProcedure

; parcours de toutes les catégories
For i = 1 To 100
  If FindMapElement(mesCat(),Str(i))
    Debug "Catégorie : "+mesCat()\nom+" parent "+mesCat()\parent
    ; appel de la procédure si renseignée
    If mesCat()\maPro
      mesCat()\maPro(@mesCat())
    EndIf
    ; appel de la procédure récursive
    chercheParent(@mesCat())
  EndIf
Next

Remarque : Les procédures récursives sont très puissantes, il faut cependant faire attention et ne pas créer un boucle sans fin

[Ar-S]

Falsam t'a répondu avec Static A
[quote=LA DOC]Static permet de créer des variables locales persistantes dans une procedure[/quote]

Dans ton code ci dessous, à chaque appel de la proce ton A vaudra 0
Peut importe ton If A < 3.. Tu peux faire If A < 12500000 que ce serait pareil
Donc tu va boucler à l'infini...

Code : Tout sélectionner

Global NumProce

Procedure MaProcedure()

  NumProce +1
  Debug "Je suis la procedure " + Str(NumProce)
  Debug "A = " + A
  
  A + 1 ; A (01) ici vaudra 1, 2
  Delay(100)
 
  If A < 3 :  MaProcedure() :  EndIf
EndProcedure

MaProcedure()

Si tu mets A en static, il gardera alors sa valeur et ta boucle se terminera quand A sera plus grand que 3.

Code : Tout sélectionner

Global NumProce

Procedure MaProcedure()
Static A
  NumProce +1
  Debug "Je suis la procedure " + Str(NumProce)
  Debug "A = " + A
  
  A + 1 ; A (01) ici vaudra 1, 2
  Delay(100)
 
  If A < 3 :  MaProcedure() :  EndIf
EndProcedure

MaProcedure()

Utilise des debugs si tu veux voir ce qu'il se passe dans tes codes, ça fait 150 fois qu'on le répète.

[falsam]

Nan moi il me plaît bien

Imprime le code et encadre le. Tu peux lui trouver une place dans tes toilettes peut être ?

Allez un peu de thread au cas ou se serait la solution que Shadow recherche peut être.

Ton ordinateur est capable de gérer plusieurs taches simultanées.

■ Exemple lancer 4 process qui vont se partager la lecture de 100 nombres.
- Le premier process va lire les 25 premiers nombres
- Le second process va lire les 25 suivants
- Etc .....

Code : Tout sélectionner

EnableExplicit

Declare Start()
Declare Process(*Numero)

; Tableau de 100 nombres
Global n = 100, Dim Table(n) 

; Quatre thread
Global Mutex, Thread0, Thread1, Thread2, Thread3

; Obligation d'activer les thread dans les options du compilateur
CompilerIf #PB_Compiler_Thread=#False
  CompilerError("Vous devez activer la gestion des Threads dans les options du compilateur !")
  End
CompilerEndIf


Start()
Procedure Start()
  Protected i
  
  ;Création de la Table
  For i = 0 To n
    Table(i) = i  
  Next
  
  Mutex = CreateMutex()
    
  thread0 = CreateThread(@Process(), 0)
  thread1 = CreateThread(@Process(), 1)
  thread2 = CreateThread(@Process(), 2)
  thread3 = CreateThread(@Process(), 3)
  
  WaitThread(thread0)
  WaitThread(thread1)
  WaitThread(thread2)
  WaitThread(thread3)  
EndProcedure

; Chaque procédure va lire une partie du tableau
; Thread0 va lire les 25 premiers nombres 
; Thread1 va lire les 25 suivants 
; etc .....
Procedure Process(*Numero) 
  Protected Segment = 25
  Protected i, n ; Cette variable sera indépendante
  Shared Mutex
  
  LockMutex(Mutex)    
  
  Debug #CRLF$ + "Le Thread " + Str(*Numero) + " lit les nombres de " + Str(*Numero * Segment) + " à " + Str(((*numero * Segment) + Segment)-1)
  
  For n = (*Numero * Segment) To ((*numero * Segment ) + Segment) - 1 
    Debug Str(i) + " Thread " + Str(*Numero) + " lecture cellule " + Str(Table(n)) 
    i + 1
  Next 
  
  UnlockMutex(Mutex)  
EndProcedure

[G-Rom]

Bonsoir, merci de vos exemple mais cela ne m'aide pas du tout !

Un souci pour les comprendre ?

Je vais te donner une explication le plus simple possible qui va détruire l'espoir que tu avais dans ces procédures récursives.

Chaque récursivité à bien ces propres variables et ne sont pas mélanger avec les autres ok ? ... j’obtiens une infinité de variable 'A' mais locale à chaque récursivité c'est bien ça ?

Suspens ....... ET BIEN NON Ha Ha Ha terminé les espoir que tu avais dans cette façon de faire



Une procédure récursive n'ira pas créer plusieurs autres procédures avec chacune ses variables indépendantes comme tu le montres dans ton exemple.

Une procédure récursive est une procédure qui s'appelle elle même à l'intérieur de sa procédure avec un certain nombre d'itérations.

Un petit exemple (Oui un de plus ^^)

Code : Tout sélectionner

Procedure MethodeCoue()
  Static RepeteDixFois
  
  RepeteDixFois + 1
  Debug "j'ai confiance en moi " + Str(RepeteDixFois) + " fois"
  
  ; On se le répéte 10 fois
  If RepeteDixFois < 10
    MethodeCoue()
  EndIf
EndProcedure

MethodeCoue()

Debug #CRLF$ + "HaaaaAAAAaaaa, ca va mieux !"

Mon exemple est moisi car sans intéret.

Je pense que le bonheur est dans le Thread ..... A suivre

Bonjour falsam, non, le principe de la récursion est de justement jouer avec des variables propre à chaque procédure...
ce petit morceau de code démontre mes dires :

Code : Tout sélectionner

Global Dim Trace.l(500)


Procedure Recursive(value.l)
  A.l = 500 - value
  If value < 500
    Trace(value) = @A
    Recursive(value + 1)
  EndIf 
EndProcedure


Recursive(0)


 For i = 0 To 499
   Debug "Adresse de A dans Recursive() = "+Str(Trace(i))
 Next

La variable A est propre à CHAQUE appel de la fonction , elle est unique , ici 500 appels donc, 500 variables différentes qui n'interfère pas d'un appel à l'autre, la preuve est que l'adresse est différente à chaque fois.
la variable est immédiatement détruite à la sortie de la procédure, donc inutile de tenter de lire le pointeur de celle ci, elle est déjà morte. pour gardé une variable d'un appel à l'autre, y a plusieurs possibilité , comme les paramètres de fonctions & les retours. Attention cependant a ne pas explosé la pile d'appel sous peine de d'erreur stack overflow. il faut préféré une méthode itérative sur des grands nombre, plus rapide et plus sur que la récursivité , celle ci doit être utilisé sur des petit nombre d'appel seulement sous peine d'exposé son programme à d'éventuel lenteur & bugs