Notes on the Use of Recursion

There have been many comments flying around the internet recently on the subject of why the use of recursive functions are fundamentally unsafe in programs. The arguments boil down to two not unrelated, points. Firstly the depth of any recursion cannot be fixed at design time, this can cause the recursion to overflow the stack capability of the platform on which it is implemented. Secondly, in the case of a stack overflow the ability to complete effective error handling and recovery is not always certain.
The two preceding points are both valid and in combination can lead to an implementation that is fundamentally disaster prone. However, there are practical implementation techniques that can help.

1. Tracking Recursion Depth

Add an additional integer parameter to your recursive function, this is set to 0 (zero) on the initial call to the recursive function. The recursive call in the function sets the parameter to the passed value plus 1 (one). This provides you with a measure of the recursion depth that can be tested on entry to the recursive function - when the level exceeds the maximum safe design depth the routine can fail gracefully and recover in a controlled manner.
It should be noted that this technique is also useful for protecting the application from heap/resource exhaustion. If, for instance, the recursive function opens a cursor, document or other similar resource, there will be limits on the number of resources that can be open concurrently. This implementation pattern allows the program design to be validated against these limits.

2. Minimising Stack Impact

The amount of stack memory used by recursive routine is equal to the per call stack memory demand multiplied by the recursion depth. The total stack memory used can be minimised by reducing the per call demand for stack memory. This can be achived by minimising the number and size of parameters passed in a recursive routine, consider passing a reference to a single structure that contains pointers, values and other parameters. Local variables also consume stack memory, consider again passing a reference to a structure that contains a collection of variables that were locally declared in the recursive routine. However, care must be taken to ensure that variables that must retain their value across the recursive call are NOT included in the passed structure BUT remain declared in the recursive routine.

3. Update on Percolation

If you do not update, serialise or commit any data in your recursive function until after the call has been made to the recursive function then the result can be determined before you make any changes. This pattern makes the atomicity of the recursion function as single unit. All data changes are percolated as the result of a successful change at the safe (see point 1 above) lowest level of the recursion. Of course all validation and preparation of the data updates must be done before the call is made to the recursive function;

bool foo(........... , depth) {    //  Check recursion limit    if (depth + 1 > MAX_RECURSION_DEPTH) return false; .    //  Validate and prepare data for update .    if foo(............. , depth + 1)    {        //  Update data        .        return true;    }    return false; }