Recursive Procedure and ProcedureReturn

Guimauve · **Posted:** Mon May 28, 2012 2:04 am

Hello everyone,

I'm sure about 99% this is a bug. In the help file, we can read :

Quote:

In PureBasic, a recurrence is fully supported for the procedures and any procedure can call it itself
...
You have to set the type after Procedure and use the ProcedureReturn keyword at any moment inside the procedure.

So if it's the case we should be able to use a ProcedureReturn to stop a procedure and return a value or string event if the procedure call it's self. But it's not the case with the following example.

Code:

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : Recursivity Bug
; File Name : Recursivity Bug.pb
; File version: 1.0.0
; Programming : OK
; Programmed by : Guimauve
; Date : 27-05-2012
; Last Update : 27-05-2012
; PureBasic code : 4.61 x64
; Platform : Linux Mint 12 x64
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Notes :
;
; The "FindFile()" original code has been created by dige 
; and extended + updated for PB 4.00 by Andre
; Date: 03. February 2005
; 
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Procedure.s FindFile(Directory.s, FileName.s)
  
  CompilerSelect #PB_Compiler_OS
      
    CompilerCase #PB_OS_Windows 
      PathSep.s = "\"
      
    CompilerCase #PB_OS_Linux
      PathSep.s = "/"
      
    CompilerCase #PB_OS_MacOS
      PathSep.s = "/"
      
  CompilerEndSelect
  
  If Right(Directory, 1) <> PathSep
    Directory + PathSep
  EndIf
  
  Debug "THE CURRENT FOLDER : " + Directory
  
  DirectoryHandle = ExamineDirectory( #PB_Any, Directory, "*.*" ) 
  
  If DirectoryHandle <> 0
    
    While NextDirectoryEntry(DirectoryHandle) 
      
      EntryName.s = DirectoryEntryName(DirectoryHandle)
      
      If Left(EntryName, 1) <> "."
        
        Select DirectoryEntryType(DirectoryHandle)
            
          Case #PB_DirectoryEntry_File
            
            If EntryName = FileName
              
              Debug "FOUND IN : " + Directory

              ; Apparently this ProcedureReturn do absolutely nothing.
              ; The procedure should stop at this point and return the 
              ; "Directory" string.
              
              ProcedureReturn Directory 
            EndIf
            
          Case #PB_DirectoryEntry_Directory 
            Debug "THE NEXT FOLDER : " + Directory + EntryName + PathSep
            FindFile(Directory + EntryName, FileName)
            
        EndSelect
        
      EndIf
      
    Wend
    
  EndIf
  
  ProcedureReturn "NOT FOUND"
EndProcedure 

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< !!! WARNING - THE FOLLOWING PROCEDURE IS NOT RELATED - WARNING !!! <<<<< 
; <<<<< !!! WARNING - TO THE BUG DEMONSTRATION CODE. IS JUST - WARNING !!! <<<<< 
; <<<<< !!! WARNING - BECAUSE I'M TOO LAZY TO PUT THE CODE   - WARNING !!! <<<<< 
; <<<<< !!! WARNING - DIRECTLY INSIDE THIS DEMONSTRATION.    - WARNING !!! <<<<< 
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Procedure.b BuiltPathDirectory(Path.s)
  
  CompilerSelect #PB_Compiler_OS
      
    CompilerCase #PB_OS_Windows 
      PathSep.s = "\"
      
    CompilerCase #PB_OS_Linux
      PathSep.s = "/"
      
    CompilerCase #PB_OS_MacOS
      PathSep.s = "/"
      
  CompilerEndSelect
  
  DirectoryQty = CountString(Path, PathSep) + 1
  
  For Index = 1 To DirectoryQty
    
    Directory.s = Directory + StringField(Path, Index, PathSep) + PathSep
    
    If FileSize(Directory) = -1
      CreateDirectory(Directory)
    EndIf 
    
  Next
  
  If FileSize(Directory) = -2
    Success.b = #True
  Else
    Success = #False
  EndIf
  
  ProcedureReturn Success
EndProcedure


; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< !!! WARNING - TESTING CODE !!! <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; Here we set a valid path in two parts, we want 
; to start the search far away from the file.

Path.s = GetHomeDirectory() + "Test Folder/"
FullPath.s = Path + "SubFolder/SubSubFolder/"

; Here we set the filename
FileName.s = "A simple text file.txt"

; Here we built an existing path

If BuiltPathDirectory(FullPath)
  
  ; we create a basic text file for testing
  
  If CreateFile(0, FullPath + FileName)
    
    WriteStringN(0, "This is a simple test !")
    WriteStringN(0, "Apparently, the recursive procedure don't work properly !")
    CloseFile(0)
    
  EndIf
  
  ; Then we try to find where the file is to test 
  ; the FindFile() function.
  
  Debug "; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"
  Debug "; FindFile() should return : " + FullPath
  Debug ""
  Debug FindFile(Path, FileName)
  
EndIf

; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<

Debugger wrote:

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; FindFile() should return : /home/guimauve/Test Folder/SubFolder/SubSubFolder/

THE CURRENT FOLDER : /home/guimauve/Test Folder/
THE NEXT FOLDER : /home/guimauve/Test Folder/SubFolder/
THE CURRENT FOLDER : /home/guimauve/Test Folder/SubFolder/
THE NEXT FOLDER : /home/guimauve/Test Folder/SubFolder/SubSubFolder/
THE CURRENT FOLDER : /home/guimauve/Test Folder/SubFolder/SubSubFolder/
FOUND IN : /home/guimauve/Test Folder/SubFolder/SubSubFolder/
NOT FOUND

Best regards.
Guimauve

Tenaja · **Joined:** Tue Nov 09, 2010 10:15 pm **Posts:** 794

Somebody has a signature that applies to you...

To understand recursion, you must first understand recursion.

Your problem is that you are not handling the return value. Every call must process every return value. You call FindFile here...

Code:

               Case #PB_DirectoryEntry_Directory
                     Debug "THE NEXT FOLDER : " + Directory + EntryName + PathSep
                     FindFile(Directory + EntryName, FileName)

But you do not receive the returned value. ProcReturn does not just halt all instances of the procedure...just the one that is executing.

Guimauve · **Posted:** Mon May 28, 2012 2:44 am

Hello everyone,

Ok my bad, I have reported this message to be moved in the "Coding Questions"

This the fully working solution (Thanks to Tenaja) :

Code:

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : FindFile
; File Name : FindFile.pb
; File version: 1.0.0
; Programming : OK
; Programmed by : Guimauve
; Date : 27-05-2012
; Last Update : 27-05-2012
; PureBasic code : 4.61 x64
; Platform : Linux Mint 12 x64
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Notes :
;
; The "FindFile()" original code has been created by dige 
; and extended + updated for PB 4.00 by Andre
; Date: 03. February 2005
; 
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Procedure.s FindFile(Directory.s, FileName.s)
  
  CompilerSelect #PB_Compiler_OS
      
    CompilerCase #PB_OS_Windows 
      PathSep.s = "\"
      
    CompilerCase #PB_OS_Linux
      PathSep.s = "/"
      
    CompilerCase #PB_OS_MacOS
      PathSep.s = "/"
      
  CompilerEndSelect
  
  If Right(Directory, 1) <> PathSep
    Directory + PathSep
  EndIf
  
  DirectoryHandle = ExamineDirectory(#PB_Any, Directory, "*.*" ) 
  
  If DirectoryHandle <> 0
    
    While NextDirectoryEntry(DirectoryHandle) 
      
      EntryName.s = DirectoryEntryName(DirectoryHandle)
      
      If Left(EntryName, 1) <> "."
        
        Select DirectoryEntryType(DirectoryHandle)
            
          Case #PB_DirectoryEntry_File
            
            If EntryName = FileName
              Output.s = Directory
              Break
            Else
              Output = "NOT FOUND"
            EndIf
            
          Case #PB_DirectoryEntry_Directory 
            Output.s = FindFile(Directory + EntryName, FileName)
            Break
            
        EndSelect
        
      EndIf
      
    Wend
    
  EndIf
  
  ProcedureReturn Output
EndProcedure 

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 
; <<<<< !!! WARNING - YOU ARE NOW IN A TESTING ZONE - WARNING !!! <<<<< 
; <<<<< !!! WARNING - THIS CODE SHOULD BE COMMENTED - WARNING !!! <<<<< 
; <<<<< !!! WARNING - BEFORE THE FINAL COMPILATION. - WARNING !!! <<<<< 
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 

Procedure.b BuiltPathDirectory(Path.s)
  
  CompilerSelect #PB_Compiler_OS
      
    CompilerCase #PB_OS_Windows 
      PathSep.s = "\"
      
    CompilerCase #PB_OS_Linux
      PathSep.s = "/"
      
    CompilerCase #PB_OS_MacOS
      PathSep.s = "/"
      
  CompilerEndSelect
  
  DirectoryQty = CountString(Path, PathSep) + 1
  
  For Index = 1 To DirectoryQty
    
    Directory.s = Directory + StringField(Path, Index, PathSep) + PathSep
    
    If FileSize(Directory) = -1
      CreateDirectory(Directory)
    EndIf 
    
  Next
  
  If FileSize(Directory) = -2
    Success.b = #True
  Else
    Success = #False
  EndIf
  
  ProcedureReturn Success
EndProcedure

CompilerSelect #PB_Compiler_OS
    
  CompilerCase #PB_OS_Windows 
    #PathSep = "\"
    
  CompilerCase #PB_OS_Linux
    #PathSep = "/"
    
  CompilerCase #PB_OS_MacOS
    #PathSep = "/"
    
CompilerEndSelect

; Here we set a valid path in two parts, we want 
; to start the search far away from the file.

Path.s = GetHomeDirectory() + "Test Folder" + #PathSep
FullPath.s = Path + "SubFolder" + #PathSep + "SubSubFolder" + #PathSep

; Here we set the filename
FileName.s = "A simple text file.txt"

; Here we built an existing path

If BuiltPathDirectory(FullPath)
  
  ; we create a basic text file for testing
  
  If CreateFile(0, FullPath + FileName)
    
    WriteStringN(0, "This is a simple test !")
    WriteStringN(0, "Apparently, the recursive procedure don't work properly !")
    CloseFile(0)
    
  EndIf
  
  ; Then we try to find where the file is to test 
  ; the FindFile() function.
  
  Debug "; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"
  Debug "; FindFile() should return : NOT FOUND"
  Debug ""
  Debug FindFile(Path, "A" + FileName)
  Debug ""
  
  Debug "; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"
  Debug "; FindFile() should return : " + FullPath
  Debug ""
  Debug FindFile(Path, FileName)  
  
EndIf

; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<

Best regards
Guimauve

Tenaja · **Joined:** Tue Nov 09, 2010 10:15 pm **Posts:** 794

Glad to be of help.

For the next guy who is searching for help on a recursive function, there are two PB tools that are helpful for debugging them. First is Debugger->Callstack, which lists the sequence of proc calls you have made--it is helpful to see how deep you are. Second is the plain debugger itself; by stepping through the code line by line you will see the progression and the return values. This is an a great program to use to learn recursion, although not necessarily an efficient use of it:

Code:

Procedure.i summer(a)
   If a > 0
      ProcedureReturn a + summer(a-1)
   Else
      ProcedureReturn 0
   EndIf
EndProcedure


debug summer(3)

If you step through it with the debugger, variable viewer, and the CallStack all showing, you should have an aha moment if it was stumping you before. You will also see how local variables are only local to the current instance of a procedure.

Guimauve · **Posted:** Mon May 28, 2012 11:43 am

I agree but some time when you see an example, your first assumption is :

Quote:

This example has been posted somewhere on the forum, so it should work as is !

But it's not the case, this the original code.

Code:

; German forum: http://www.purebasic.fr/german/viewtopic.php?t=1892&highlight=
; Author: dige (extended + updated for PB 4.00 by Andre)
; Date: 03. February 2005
; OS: Windows
; Demo: Yes

; FindFile: recursice file search

; FindFile : Rekursive Datei-Suche 
; by DiGe german forum 03/02/2005 

Procedure.s FindFile ( Directory.s, File.s ) 
  found = #False
  DirNr = ExamineDirectory( #PB_Any, Directory, "*.*" ) 
  If DirNr 
    Repeat 
      Ergebnis = NextDirectoryEntry(DirNr) 
      If Ergebnis = 1 
        If File = DirectoryEntryName(DirNr) 
          Debug "Gefunden in : " + Directory
          ProcedureReturn Directory 
          found = #True
        EndIf 
      ElseIf Ergebnis = 2 And DirectoryEntryName(DirNr) <> ".." And DirectoryEntryName(DirNr) <> "." 
        FindFile ( Directory + "\" + DirectoryEntryName(DirNr) , File.s ) 
      EndIf 
    Until Ergebnis = 0 
  EndIf 
  If found = #False
    ProcedureReturn "NOT FOUND"
  EndIf
EndProcedure 

Debug FindFile( "C:\Windows", "actmovie.exe" ) 

Anyway, the Recursion concept are, for me, one of the most difficult ones.

Best regards
Guimauve

PureBasic Forum

Recursive Procedure and ProcedureReturn

Who is online