Recursion is a

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.

Consider Recursion when:

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 Booth 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 )