Home for HMNL Enterprise Computing

Enterprise Computing

Some Notes on the Use of Recursion

Ian Tree  01 March 2008 15:45:30

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. 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;

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;
}


Share: