Recursion

This page is an example of bound recursion.

If you've already read this page, please stop reading now. Otherwise, please continue.

To be useful, recursion needs to have boundary conditions, base cases, exits, limitations: things that stop it from running on forever and ever and ever and ever and ever and ever and, so on in an infinite regress.

Stack Depth Counter

One idea to avoid infinite regress is to use a "stack depth counter" -- a variable that is incremented each time a method calls itself. And a condition which exits when the "depth" of the stack passes some critical threshold.

Choosing a suitable threshold can be referred to as either "a matter of trial and error" or as "an art unto itself" or as "the fundamental skill which an engineer seeks to attain." If a value is too small, then a "false positive" may be encountered where the program thinks it is in a cycle, but is simply in a deep part of the structure. If a value is too large, then cycles are wasted, and the program risks using up available resources (e.g. throwing a stack overflow exception).

The threshold may also be passed in and may even be manipulated depending on the prevailing conditions.

Limit

A complementary idea to a stack counter is to pass in a "limit" variable which is decremented each time a method calls itself. If the limit is at zero, then the method exits.

The above methods are examples of "heuristics" -- in-exact algorithms. It is certainly possible to create exact algorithms for detecting cycles. We'll cover that next.

Traversing with Recursion

Recursion is often used as a method of traversing (or navigating) over complex data structures. Linked lists, binary trees, R-Trees, and so on.

In those cases, it is hoped that the data structure is 'well-formed' and doesn't include any loops that would lead to infinite regress (officially these are called 'cycles')(Don't call them loops: you sound silly when you call them loops.).

Because these sort of data structures (linked-lists, trees) do not automatically make loops illegal, so it can be necessary to write routines that detect loops. I mean cycles. This is considered pretty wizard stuff, and is even used as an interview question at some pretty top notch organisations. If you're ever faced with questions on this topic just walk to the whiteboard and draw a picture of a tortoise and a hare. After that, the job is yours.

If you haven't yet read about about recursion, please read this page

If you can never read enough about recursion please read about unbounded recursion.

External Links

See Also