Do you know where your variables are? PerlMonks

### Misunderstanding Recursion

by Andrew_Levenson (Hermit)
 on Dec 15, 2006 at 21:44 UTC Need Help??
Andrew_Levenson has asked for the wisdom of the Perl Monks concerning the following question:

Last night I happened upon DigitalKitty's Recursion: The Towers of Hanoi problem, which opened my eyes to the world of recursion (thanks for that, by the way). Never had the thought occurred to me that I could call a loop from within that loop. So I revisited my old prime script with this new tool in hand.

After toying with it a bit, I gave it a go. Extremely fast for up to 1000. Then it started to slow down, which puzzled me. When doing up to one million (not a problem for previous versions) it got hung up around 700,000.

Why, oh why, fellow monks, does this script
\$n=1; \$lim=1000000; print "2 "; prime(\$n+=2); sub prime{ exit if \$n>=\$lim; for(\$i=3;\$i<=sqrt(\$n);\$i+=2){ prime(\$n+=2) if \$n/\$i==int(\$n/\$i); } print "\$n "; prime(\$n+=2) if \$n<\$lim; }

run so much slower than this script?
use strict; use warnings; for my \$i(2..1000000){ print "\$i " if \$i==2; my \$even=0; my \$notprime=0; my \$j=\$i/2; next if int(\$j)==\$j; my \$n=\$i**(1/2); for(3..\$n){my \$o=\$i/\$_; \$notprime=1 if int(\$o)==\$o; last if int(\$o)==\$o;} print "\$i " if \$even==0 && \$notprime==0; }

From my (severely limited) point of view, it should run a lot faster/be more efficient than the latter. Is there some feature of recursion that I don't know about that is causing me to choke?

C(qw/74 97 104 112/);sub C{while(@_){\$c**=\$C;print (map{chr(\$C!=\$c?shift:pop)}\$_),\$C+=@_%2!=1?1:0}}

Replies are listed 'Best First'.
Re: Misunderstanding Recursion
by chromatic (Archbishop) on Dec 15, 2006 at 21:53 UTC

To support things like caller, Perl (and other languages) use something called call frames. This is an internal data structure that represents a single call into a subroutine. (That's sort of a convenient lie; it's not quite an internal data structure in Perl, but it's a convenient fiction.)

Every time you call a new subroutine, Perl makes a new call frame and executes more code. All of those calls add up.

There is a particular program optimization called tail recursion that a compiler can perform when it notices that the last call into a subroutine is recursive, but Perl 5 doesn't do that. (It's too bad, because it can save lots of memory and time, and it's not difficult to get back the accounting information that caller might need.) There are other optimizations too that allow you to transform recursive calls into iterative calls, but Perl doesn't do those for you either.

Re: Misunderstanding Recursion
by Joost (Canon) on Dec 15, 2006 at 21:57 UTC
You're probably running out of memory: every recursive subroutine call will take up some amount of memory until it returns. By the way, your code looks very strange: you're passing all kinds of parameters to prime() but you never use them. Instead you appear to be modifying global variables. In fact, it doesn't really look like a "traditional" recursive algorithm at all.

You really should use strict and warnings.

Huh, looks like I understand these things even less than I thought.
C(qw/74 97 104 112/);sub C{while(@_){\$c**=\$C;print (map{chr(\$C!=\$c?shift:pop)}\$_),\$C+=@_%2!=1?1:0}}
Hey Andrew, this is just a belated reply concerning perl's argument handling. I'm typing this because I've got the feeling you've missed something there :-)

Perl subroutines get their arguments in the special @_ array, like this:

foo(1,2,3,4); sub foo { my (@args) = @_; # now @args holds a _copy_ of all the arguments }
this extends to any and all subroutine argument handling in perl - the only way to get a hold of arguments is to directly or indirectly read from the @_ array. shift() and pop() without further arguments do this implicitly:
sub foo { my \$first = shift; # get the first argument and remove it from @_; my \$last = pop; # get the last argument and remove it from @_; }
Note that your code above does not do anything with the supplied arguments, it just uses the variables as supplied in the global scope. that means that when the variables are modified in the subroutine, that also modifies the variables in the global scope and in the recursive calls, since they are all the same variable.

Note also that this code:

my \$i = 1; inc(\$i); sub inc { \$i++; #note: \$i is not declared and read from @_ }
does not do the same as:
my \$i = 1; inc(\$i); sub inc { my \$i = shift; # declare and read \$i from @_ \$i++; }

In the first example, the outer-scope \$i is increased, while in the second example only the \$i local to the inc() sub is increased. There's lots of pretty subtle and interesting stuff going on in this simple example. You might start by reading perlsub and/or searching for lexical variables and closures here on perlmonks.

Instead you appear to be modifying global variables. In fact, it doesn't really look like a "traditional" recursive algorithm at all.

In which case, if one really needed to do so, then it may be better to use magic goto rather than standard sub call.

Re: Misunderstanding Recursion
by jbert (Priest) on Dec 15, 2006 at 22:39 UTC
As others have mentioned, each level of recursion (or, more generally, each function down from the top-level) has something called a stack frame, which records information.

This isn't just to support caller, it's a very common feature of most languages. If nothing else, it generally contains the information of where to jump to when you return from the current subroutine and the values of the lexical variables which are in that scope but not in the current scope 1.

It's not to everyone's taste, and it uses a different language, called scheme, but the online textbook "Structure and Interpretation of Computer Languages" or SICP covers this, in this section (and related pages).

Recursion is a powerful tool, and like all such it can be mis-used. In particular, note that the amount of stack space is limited on different platforms. Some Win2k systems give you 2mb of stack (by default). If you have a recursive routine which has a 64k variable in the stack frame, you'll die after 30 recursions or so. (This was a real-world bug in a C program).

1: OK, so lexicals may be stored seperately from the call stack, since you can have intermediate scopes. The same principle applies though.

Re: Misunderstanding Recursion
by throop (Chaplain) on Dec 15, 2006 at 22:42 UTC
What I recall from studying LISP some quarter-century ago: For any recursive solution to a problem, there also exists an iterative solution. Because of the overhead of subroutine calls, the iterative solution usually runs faster and with less memory. Indeed, tail-recursion is essentially a way of turning a recursive solution into an iterative one.

BUT!

The most important measure of speed is the programmer's speed in writing the code, the reviewer's speed in deciding if it's correct, and the maintainer's speed of understanding it. In the cases where they're appropriate, recursive solutions are often much more compact and clear than the iterative solution.

When is a recursive solution more appropriate than an iterative one? If you've got a set of objects and you need to solve a case for each one, and the solutions aren't all linked together, iterate. But if your data structure looks more like a tree or a graph, look for a recursive solution. Given a hard case, can you shave off part of the problem and turn it into a very similar problem, only smaller? Recurse.

throop

Re: Misunderstanding Recursion
by ikegami (Pope) on Dec 15, 2006 at 22:46 UTC

Bug! The for loop from one call to prime can clobber the \$i of a loop in progress in a parent call.

for(\$i=3;\$i<=sqrt(\$n);\$i+=2){
should be
for(my \$i=3;\$i<=sqrt(\$n);\$i+=2){

Use use strict!

Re: Misunderstanding Recursion
by samtregar (Abbot) on Dec 15, 2006 at 22:53 UTC
As you've discovered, recursion isn't very time or space efficient, compared to iteration. However, don't toss it out of your toolbox completely - it's very useful dealing with bounded data-structures where you know in advance the maximum depth. I use recursion all the time when dealing with small trees (XML parse trees, category hierarchies, etc.).

The intimate relationship between recursion and iteration is a major theme in Higher Order Perl. Pick up a copy and blow your mind today!

-sam

Re: Misunderstanding Recursion
by swampyankee (Parson) on Dec 15, 2006 at 23:04 UTC
it should run a lot faster/be more efficient than the latter

While recursion may make for much simpler code, it will not necessarily make for faster/more efficient code tail recursion is better in this regard. A classic example is calculation of factorials. In my, doubtless horrid, example:

#!perl use strict; use warnings; use diagnostics; use Benchmark qw(:all); #print 'looping: ' . looping(10) . "\n"; #print 'recursive: ' . recursive(10) . "\n"; my \$count = -5; cmpthese(\$count,{ recursive => sub{&recursive(50)}, looping => sub{&looping(50)}}); sub recursive { my \$x = shift; if(\$x <= 1) { return 1; } else{ return \$x * recursive(\$x - 1); } } sub looping { my \$x = shift; my \$y = 1; foreach my \$z (1 .. \$x) { \$y*=\$z; } return \$y; }

I got these results:

Rate recursive looping recursive 9228/s -- -77% looping 39979/s 333% --

Which, if I interpret it correctly, shows the looping sub is quite a bit faster.

Of course, this does not mean that all recursive routines that can be replaced by iterative routines should be; this is likely to be misplaced optimization. There are a great number of cases where the code written with recursion is going to be much simpler, which means that it will globally be better: more reliable, easier to test, easier to understand, quicker to get right.

emc

At that time [1909] the chief engineer was almost always the chief test pilot as well. That had the fortunate result of eliminating poor engineering early in aviation.

—Igor Sikorsky, reported in AOPA Pilot magazine February 2003.

The multiplication happens after the recursive call in your snippet, so your snippet isn't tail recursive. The following is a tail recursive version of your snippet:

sub _tail_recur { my (\$x, \$y) = @_; if (\$x <= 1) { return \$y; } else { return _tail_recur(\$x - 1, \$x * \$y); } } sub tail_recur { my (\$x) = @_; return _tail_recur(\$x, 1); }

Tail recursion allows for the compiler to automatically flatten recursion (slow, and memory usage is proportional to the recursion depth) into a loop (fast, and memory usage is constant). Unfortunately, Perl5 does not do tail-recursion optimization.

Re: Misunderstanding Recursion
by ph713 (Pilgrim) on Dec 15, 2006 at 23:05 UTC
As some have already said, recursion can be expensive in perl. As a real-world example, compare the algorithms in Algorithm::C3 0.01 vs 0.06:

The 0.01 version of the algorithm is recursive, whereas the 0.06 version is an iterative refactor. As indicated by throop above, you can see that the algorithm became much more complex and difficult to maintain and debug as a result. Adding to the ugliness is the fact that the recursive version of this algorithm cannot be transformed into a tail-recursive version, which is usually the first step in a simple transformation to iteration. The only way to transform this one was by making our own stack to simulate the call stack of the recursive version.

In this case it was worth it, as the iterative approach is noticeably faster, it's a low-level module that other big modules use, and profiling apps that use it show it to be a performance hotspot.

Transforming recursion to iteration is a performance win in Perl, but there's always the tradeoffs to consider.

Re: Misunderstanding Recursion
by runrig (Abbot) on Dec 16, 2006 at 00:43 UTC
Just to add to the general discussion, you can sometimes simulate tail recursion optimization by setting the argument list and using goto function:
sub some_function { ... @_ = @new_list_of arguments goto &some_function ... }
But even this is not very efficient in Perl compared to iteration and normal recursion (though if the recursion is deep, this is an option...though iteration is most likely a better option). (Update: so it could be considered a memory optimization over normal recursion, but definitely not a speed optimization).
…this is not very efficient in Perl…
You may refer to some disappointing benchmark as this:
Rate goto_recur recursive tail_recur looping goto_recur 3437/s -- -59% -60% -90% recursive 8472/s 147% -- -1% -76% tail_recur 8569/s 149% 1% -- -76% looping 35417/s 931% 318% 313% --

where the benchmark is that of swampyankee above, adding ikegami's tail_recur and a derived version of that using your goto recipe:

sub _goto_recur { my (\$x, \$y) = @_; if (\$x <= 1) { return \$y; } else { @_ = (\$x - 1, \$x * \$y); goto &_goto_recur; } } sub goto_recur { my (\$x) = @_; return _goto_recur(\$x, 1); }
Then I was surprised that throwing out all lexicals and directly messing with @_ yields more pleasing results:
sub _goto_recur { if (\$_[0] <= 1) { return \$_[1]; } else { \$_[1] *= \$_[0]; --\$_[0]; goto &_goto_recur; } } sub goto_recur { my (\$x, \$y) = (shift, 1); # We can't plug the constant 1 directly into \$_[1] # since we want to change that (alias!) return _goto_recur(\$x, \$y); }
Gives on my machine:
Rate recursive tail_recur goto_recur looping recursive 8456/s -- -1% -9% -77% tail_recur 8519/s 1% -- -8% -76% goto_recur 9278/s 10% 9% -- -74% looping 36011/s 326% 323% 288% --
Of course that code does not look very desirable from a maintainers point of view.
Then I was surprised that throwing out all lexicals and directly messing with @_ yields more pleasing results:
Except that it has the unpleasant side effect of modifying the caller's argument list :-)
Re: Misunderstanding Recursion
by shotgunefx (Parson) on Dec 15, 2006 at 23:15 UTC
A good example of recursion (and the potential difficulties) is a Flood fill subroutine.

I wrote my first one on a 4mhz Tandy 1000, hit the limits on that pretty fast. Looking at how various other algorithms work to get around those issues would probably be informative as well.

-Lee
"To be civilized is to deny one's nature."
Re: Misunderstanding Recursion
by DigitalKitty (Parson) on Dec 15, 2006 at 23:22 UTC
Last night I happened upon DigitalKitty's Recursion: The Towers of Hanoi problem, which opened my eyes to the world of recursion (thanks for that, by the way).

Hi Andrew_Levenson.

You're very welcome.
Re: Misunderstanding Recursion
by Cabrion (Friar) on Dec 17, 2006 at 20:36 UTC

Create A New User
Node Status?
node history
Node Type: perlquestion [id://590122]
Approved by Old_Gray_Bear
Front-paged by friedo
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (6)
As of 2018-06-22 05:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (121 votes). Check out past polls.

Notices?