Deep recursion problem

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));

  }

}
[download]

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

Replies are listed 'Best First'.
Re: Deep recursion problem by ikegami (Patriarch) 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.	[reply] [d/l] [select]
Re^2: Deep recursion problem by hexcoder (Curate) on Feb 01, 2013 at 16:37 UTC
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> ...` [download] This is now part of my debugger initialization file.	[reply] [d/l]
Re^3: Deep recursion problem by ikegami (Patriarch) on Feb 11, 2013 at 23:02 UTC
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. ...` [download] See the post to which you replied if you want to know what `$DB::deep` actually does.	[reply] [d/l] [select]
Re: Deep recursion problem by davido (Cardinal) 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	[reply] [d/l]
Re: Deep recursion problem by RichardK (Parson) 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;`	[reply] [d/l]
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));` [download]	[reply] [d/l]
Re: Deep recursion problem by TGI (Parson) 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; }` [download] 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	[reply] [d/l] [select]


We don't bite newbies here... much
	PerlMonks