Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Deep recursion on subroutine

by Dr Manhattan (Beadle)
on Sep 04, 2013 at 12:36 UTC ( #1052325=perlquestion: print w/ replies, xml ) Need Help??
Dr Manhattan has asked for the wisdom of the Perl Monks concerning the following question:

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

Comment on Deep recursion on subroutine
Re: Deep recursion on subroutine
by choroba (Abbot) on Sep 04, 2013 at 12:39 UTC
    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.
    لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
Re: Deep recursion on subroutine
by hdb (Prior) on Sep 04, 2013 at 12:56 UTC

    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.

Re: Deep recursion on subroutine
by NetWallah (Abbot) on Sep 04, 2013 at 13:38 UTC
    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.

                 My goal ... to kill off the slow brain cells that are holding me back from synergizing my knowledge of vertically integrated mobile platforms in local cloud-based content management system datafication.

Re: Deep recursion on subroutine
by davido (Archbishop) on Sep 04, 2013 at 15:38 UTC

    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.


    Dave

Re: Deep recursion on subroutine
by Laurent_R (Parson) on Sep 04, 2013 at 18:03 UTC

    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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1052325]
Approved by davies
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (11)
As of 2014-09-16 07:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (157 votes), past polls