Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Deep recursion problem

by etheral (Acolyte)
on Oct 21, 2011 at 14:54 UTC ( #932918=perlquestion: print w/ replies, xml ) Need Help??
etheral has asked for the wisdom of the Perl Monks concerning the following question:

use strict; use warnings; no warnings 'recursion'; use Pod::Usage; use English qw( -no_match_vars ); use Getopt::Long qw(:config no_ignore_case no_auto_abbrev pass_through +); $OUTPUT_AUTOFLUSH = 1; #################################################################### ## OPTIONS #################################################################### GetOptions( "help|h!" => \my $help, ) or pod2usage(verbose => 0,exitstatus => 1); if ($help) { pod2usage(verbose => 2,exitstatus => 0); exit; } #################################################################### ## MAIN #################################################################### my @array = (1 .. 150); my $array_size = size_of_an_array(@array); print "Size of this array is $array_size\n"; exit; #################################################################### ## SUBS #################################################################### sub size_of_an_array { my(@array) = @_; if (not @array) { return 0; } else { pop @array; return (1 + size_of_an_array(@array)); } }

This code works ok because I removed recursion warning (line on top of the code). If I allow recursion warning and my array is (1 .. 98) I get no warnings. If my array is larger I get Deep recursion on subroutine "main::size_of_an_array" at ./recursive_array_ex11.8.pl line 91.. On the net I found it has something to do with perl's depth limit being 100, and that there is a $DB:deep variable that allows you to change this depth. But I can't figure how it works, could you help me solve this problem (I'd like to have a very large array, use this recursive subroutine, and get no warnings)

Comment on Deep recursion problem
Download Code
Re: Deep recursion problem
by RichardK (Priest) on Oct 21, 2011 at 15:06 UTC

    Well -- Why do you want to do such a strange thing ? perl isn't haskell you know ;)

    Anyway perl arrays know how big they are, just ask them

     my $size = @array;
Re: Deep recursion problem
by jethro (Monsignor) on Oct 21, 2011 at 15:10 UTC

    DB:: is AFAIK the namespace of the debugger, so only the debugger will use that variable. If you want to recurse deeply, then just use "no warnings 'recursion';", as you already found out. Such a warning would have no value to you when you want to do arbitrarily deep recursion anyway.

    And if you really need a limit, count the recursion yourself with an additional parameter (clunky but effective):

    sub size_of_an_array { my($i, @array) = @_; ... return(++$i, 1 + size_of_an_array(@array));
Re: Deep recursion problem
by ikegami (Pope) on Oct 21, 2011 at 16:56 UTC

    it has something to do with perl's depth limit being 100

    It's not a limit. Perl will happily continue to recurse until it runs of memory. It just warns you when you reach a depth of 100.

    and that there is a $DB:deep variable that allows you to change this depth.

    No there isn't. $DB::deep instructs the debugger to break at a certain recursion depth. It has no effect outside the debugger, and it doesn't affect the warning because the warning is always disabled when using the debugger.

    As stated in perldiag, "this threshold can be changed from 100, by recompiling the perl binary, setting the C pre-processor macro PERL_SUB_DEPTH_WARN to the desired value."

    I'd like to have a very large array, use this recursive subroutine, and get no warnings

    That's what no warnings 'recursion'; is for.

      As stated in perldiag, "this threshold can be changed from 100, by recompiling the perl binary, setting the C pre-processor macro PERL_SUB_DEPTH_WARN to the desired value."

      Hmmm... there are two cases: with or without running the debugger. I assume you meant the case without the debugger.

      With the debugger, one can set the threshold higher than 100 interactively prior to running the program, for example:

      DB<1> $DB::deep=1000 DB<2> ...

      This is now part of my debugger initialization file.

        Hmmm... there are two cases: with or without running the debugger. I assume you meant the case without the debugger.

        No, I meant what I said. $DB::deep has no effect on the warning. Ever.

        With the debugger, one can set the threshold higher than 100 interactively prior to running the program

        That's not true.

        >perl -dwe"$DB::deep = 1000; sub f { f($_[0]-1) if $_[0]; } f(150);" Loading DB routines from perl5db.pl version 1.37 Editor support available. Enter h or 'h h' for help, or 'perldoc perldebug' for more help. main::(-e:1): $DB::deep = 1000; sub f { f($_[0]-1) if $_[0]; } f(150 +); DB<1> r Deep recursion on subroutine "main::f" at C:/Progs/perl5161-ap1601/lib +/perl5db.pl line 3550. at C:/Progs/perl5161-ap1601/lib/perl5db.pl line 3550. ...

        See the post to which you replied if you want to know what $DB::deep actually does.

Re: Deep recursion problem
by davido (Archbishop) on Oct 21, 2011 at 17:05 UTC

    Turning on use diagnostics; will give you a more meaningful warning, which may explain why there is a warning when you reach 100:

    Deep recursion on subroutine "main::recurse" at mytest.pl line 11 (#1) (W recursion) This subroutine has called itself (directly or indirectly) 100 times more than it has returned. This probably indicates an infinite recursion, unless you're writing strange benchmark programs, in which case it indicates something else.

    This threshold can be changed from 100, by recompiling the perl binary, setting the C pre-processor macro PERL_SUB_DEPTH_WARN to the desired value.

    Keep in mind that recursion is often seen as a simple means of traversing a binary tree or doing binary searches; O(log n) operations for balanced trees. A tree size would have to be greater than 2.7e43 elements for you to reach the recursion max warning in an efficiently designed recursive tree-traversal or binary search algorithm. ...and when you exceed that many function calls on the call stack the speed of an iterative approach begins to weigh in favorably against recursion. Recursion can be used for many other things though, so Perl lets you lift the warning.


    Dave

Reaped: Re: Deep recursion problem
by NodeReaper (Curate) on Oct 22, 2011 at 12:34 UTC
Re: Deep recursion problem
by TGI (Vicar) on Oct 23, 2011 at 02:12 UTC

    If you want to do this kind of recursion, avoiding all the copying will make things faster.

    Note that I am too lazy to even try a comparison using Benchmark to prove what I say. So I could be deluding myself here.

    This code should be a fair bit faster than yours:

    sub size_of_an_array { return 0 unless @_; pop; return 1 + &size_of_an_array; }

    The reason for the putative speed boost is that it avoids making any copies of the array under consideration.

    Check out perlsub for the meaning of &sub_name;.

    If you care to benchmark, you might find that shift works even faster than pop. It is a very frequent operation on @_, so I wouldn't be surprised if there are clever optimizations there.

    You also might find that I'm full of it. Surprising things can happen. That's why you should always benchmark and profile code when you try to optimize it. That way you can be sure you are making effective optimizations on the right parts of the code.


    TGI says moo

Reaped: Re: Deep recursion problem
by NodeReaper (Curate) on Oct 24, 2011 at 12:58 UTC
Reaped: Re: Deep recursion problem
by NodeReaper (Curate) on Oct 26, 2011 at 12:53 UTC

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (16)
As of 2014-08-27 13:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (238 votes), past polls