Deep recursion on subroutine

[Dr Manhattan]

Hi all

I have a script using recursion to traverse a tree. I get a 'deep recursion on subroutine' warning. The tree is quite large so I'm assuming that I will take a while. But how can I be sure this thing won't go on infinitely? Can I be sure that it will eventually stop? I've tried to read up on it but I can't find any clear answers.

Thanks in advance for any help, much appreciated

[choroba]

From the theoretical perspective, you can be never sure. But, in practice, your computer will run out of memory far before going into infinite recursion. If you can find an upper bound of the depth (e.g. the size in bytes of the input file), you can check whether your current depth is not beyond the bound.

[hdb]

If it takes long time to traverse the tree because of some time-consuming action you take on each node, you might want to write a lighter version of your crawler that does nothing but to traverse the tree. This is no guarantee that the 'real' thing will not hang but will give you some confidence.

You could also add some bookkeeping to make sure you have not visited a node already, for example because you have circular structures in the 'tree' that you were not aware of, or because of some bug.

[NetWallah]

Add a $recursion_depth parameter to your sub - initialize to zero on the initial call.

Add one on each recursive call.

When the value exceeds some "reasonable" number corresponding to the max expected depth, call "Carp" and bail.

[davido]

The warning can be squelched easily enough. perllexwarn should identify which class of warnings to eliminate.

But the warning could be an indication of a bigger problem (and usually is). Imagine doing a traversal of a binary tree. A *balanced* tree with a million nodes would require 20 levels of recursion to traverse (assuming a recursive approach). Deep recursion warnings come after 100 levels of recursion, if I'm not mistaken. So either the algorithm being used is inefficient, or the tree isn't balanced, or there's a bug resulting in runaway recursion.

If the tree isn't balanced, it's probably time to start looking in the datastructure cookbook again. ;)

This isn't to say that there's no legitimate use of deep recursion; there is. But Perl isn't "tail call optimized", so when you start getting to the point that you're encountering deep recursion, an iterative approach would probably be more efficient anyway. An example: A linear search of a linked list can be written beautifully with recursion, but would hit the "deep recursion" warning with just 100 nodes. One could push on beyond that, but an iterative approach would expend fewer cycles on the linear search.

[Laurent_R]

The way to silence the warning, if you are *really* sure that your program and your data will not lead you into too deep (or "infinite") recursion:

no warnings 'recursion';

This warning otherwise occurs when you go beyond 100 recursion levels. There are cases where you may be happy to go to 1000 levels.