wiki.secretGeekWhat Links Here?
Outbound Links
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 etc.) do not automatically make loops illegal, 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.
The idea of the hare and the tortoise algorithm is that you carefully trace your way through the data structure, using a pointer to keep track of where you are up to. Imagine you are using your left hand, which we will call “tortoise”, to point to the node you are currently at. At the same time, you also use your right hand to traverse through the same data structure, starting at the same place and headed in the same direction. But the twist is this: you call your right hand “hare” — a hare being a creature that is somewhat faster than a tortoise. And since you’ve named that hand “hare” you won’t be surprised to hear that you ensure your right hand makes two moves for every move your left hand makes. So with both hands travelling through the data structure, one moving twice the speed of the other, one of two things will happen. Either, the hare will reach the end, in which case you know there were no infinite loops, I mean cycles. Or, the hare, despite racing through the data structure at twice the speed of the tortoise — will suddenly run into the tortoise, up ahead of him. I’m which case you know you’ve been going in circles all along. At that point you perform an elaborate little dance and say things like “voilà!” The dance isn’t strictly needed, but it’s highly recommended.
Anyhoo, at this point I have two things left to say:
If you haven't yet read enough about recursion, please read this page
If you can never read enough about recursion please read about unbounded recursion.