Wiki Home

Recursion In VFP


Namespace: Wiki

A place to discuss recursion in VFP.

Recursion is a procedural programming pattern wherein a procedure/function calls itself. It is usually used as an alternative to some sort of standard looping structure.

(Recursion is often an Object Oriented programming pattern, particularly when objects associated via composition or aggregation polymorphically traverse the structure (via calls to the same method in each child object). Even simpler, any object method can call itself, thereby being recursive.)
Is the former (objects calling other object's methods to traverse a run-time structure) true recursion? Or is there another word to describe this behaviour?

For example, an iterative function which determines the factorial of the argument may look like this:
FUNCTION Factorial1
LPARAMETER n
LOCAL y,x
y=1
FOR i=2 TO n
	y=y*i
ENDFOR
RETURN y 

Rendered as a recursive function, the same effect (with some restrictions, see below) can be obtained as follows:
Function Factorial2
LParameter n
 * RETURN iif(n>1,n*Factorial2(n-1),n)
RETURN iif(n>1,n*Factorial2(n-1),1)


Modification to support calling Factorial2(0) which should be 1, not 0 -- Chad Bourque

Recursion can be a useful tool when performing a possibly undetermined number of self similar operations.
It is a good measure of the usefulness of a recursive solution to determine if the nature of the problem is recursive. (Well, calculation factorials is not IMHO --Kurt) Problems like directory trees, object hierarchies, and bill of materials explosions are, by nature, recursive problems and can be well suited to recursive solutions.

In any programming language, there are some important considerations to make in the use of recursion. Recursive functions typically take more system resources to complete than the same work in an iterative version of the same function. In particular, the memory available must be able to support the entire recursive stack prior to resolution. Some languages will limit the nesting level of function calls independently of the available memory. (VFP is one of these.)

In VFP, these limitations play out in the form of two Visual FoxPro Limits:
Limitation
How to Check
1. Maximum Do Loop count: This limitation caps the recursive stack to 128.
VFP 9 can now nest DOs deeper than 128 levels. Steve Derzi
A simple program() call can test to see if you are near the limit and provide a controlled abnormal termination of the routine.
2. MVCOUNT: Your VFP config settings will establish the maximum number of memory variables allowed. Default is 1024 and max is 65,000. Each recursive call will add another set of the locals to the total in use. Your code is likely to hit this limitation long before you actually run out of memory.
Programmatically determining your MVCOUNT can be done two ways: You can use a sys() function to find the config.fpw file and read it or you can read the output of a LIST MEMORY TO FILE command.



Of course, if the situation is such that these limits cannot be reached, checking for them is not necessary.

A couple of functions provided by David Frankenbach that won't ever come close to the limits:
This function returns the full object containership name, I wrote it before the SYS() function existed.
* FullName.prg  13-Jun-95

* Generate an object's full containership name

* 03-Dec-95 added additional validity testing
* 26-Apr-96 added testing to handle _VFP object which is its own .Parent
* 15-Jan-98 used IsObject()
* 12-Nov-98 added testing for Name property

function FullName( roObject )

if ( IsObject( m.roObject ) and ;
     ( type( "roObject.Name" ) == 'C' ) )
   if ( ( type( "roObject.Parent" ) == 'O' ) and ;
        ( roObject.Name != "Microsoft Visual FoxPro" ) )
      return ( FullName( roObject.Parent ) + "." + roObject.Name )
   else
      return roObject.Name
   endif
else
   return ""
endif

This one gets all files of a directory tree. Practically one can not create a directory tree so deep that this function won't work. if the user has a tree that consists only of single character names c:\a\b\c\d\e\f\g\... then it could fail.
ltStart = datetime()

create cursor tempfiles ( cFilename c(80), nSize n(10), dMod d )

RecurseFolder( "c:\" )
? datetime() - ltStart

index on nSize tag nSize

browse nowait

function RecurseFolder( lcDir )
local i,n, laFiles[1]

?? "."
n = adir( laFiles, lcDir + "*.*", "shd" )

for i = 1 to n
   if ( left( laFiles[i,1], 1 ) != '.' )
      if ( "D" $ laFiles[i,5] )
         RecurseFolder( lcDir + laFiles[i,1] + "\" )
      else
        insert into tempfiles ;
               values( lcDir + laFiles[i,1], laFiles[i,2], laFiles[i,3] )
      endif
   endif
endfor
return

The object inspector that I wrote for the ProsTalk OOP book used a recursive method to find all contained objects.


Traverse directories to find all files function

Recursive routines can always be rewritten as iterative ones if you think they will tax the system limitations. Indeed, the iterative version will likely be faster. As an example, consider the following comparison of the factorial functions above.


Also note the iterative function does not suffer from the requirement that n<=127 (at least one of the 128 do's is needed to house the prg in which the function lives).

End-recursive routines (routines with only one recursive call which is the first or the last statement) can always easily be rewritten as loop. The worst case is implementing a stack by oneself (which is actually like simulating the recursion). I doubt that this is significantly faster than a recursive implemention.

General Guidelines

Consider Recursion when:
  • The problem is recursive in nature
  • The size of the recursive stack will be self-limiting and not determined (directly or indirectly) by the user
  • The resulting code will be significantly clearer than with a loop
  • Performance is not an issue relative to code readability
    Useful References:
    In General: http://swww.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html
    In Particular: http://swww.ee.uwa.edu.au/~plsd210/ds/dynamic.html
    In General: http://hissa.nist.gov/dads/
    In Particular: http://hissa.nist.gov/dads/HTML/recursion.html
    Contributors: Lauren Clarke David Frankenbach Zahid Ali Jim BoothOffsite link to http://www.jamesbooth.com
wgcs Chad Bourque Steve Derzi
    See Also Recursive Directory Processing
    Category Learning VFP Category 3 Star Topics
  • ( Topic last updated: 2016.07.29 09:29:46 AM )