XP is just a number PerlMonks

Re^4: Behold! The power of recursion.

by stvn (Monsignor)
 on Oct 18, 2004 at 15:52 UTC ( #400188=note: print w/replies, xml ) Need Help??

in reply to Re^3: Behold! The power of recursion.
in thread Behold! The power of recursion.

As with any tool, its all about how you use it.

The common misconception is that recursion is inefficient because each iteration entails calling a subroutine. In a lot of langauges, this means allocating a stack frame and freezing the previous stack frame until the next one exits. This can quickly eat up recourses, and depending upon the complexity of the recursion, leave a number of half finished computations. The result is that your function takes up exponetntial memory/stack/resource space. A common technique to avoid this in Scheme and other languages (even including C with the right compiler) is called Tail Call Optimization.

Tail Call Optimization is possible when you have a Tail Recursive function. A Tail Recursive function is a function where the last value (the return value) is the point of recursion. (Since this is a very common form for recursive functions, it works out well.) For instance, most factorial implementations are (for the most part) tail recursive but may not be eligible for tall call optimization, take this one for example:

```sub factorial {
my (\$n) = @_;
if (\$n == 0) {
return 1;
}
return \$n * factorial(\$n - 1);
}
It will do most of the bad things I mentioned above (except that Perl doesnt use a stack like C does). Each recursion is waiting on the next recursion before it can perform the multiplication. This type of function is very hard for a compiler to optimize because each recursion depends upon the next one to complete its work.

And now (keeping in mind that the particular compiler must do the real optimization) take a look at this modification of the factorial function. It is still recursive, but it has been modified so that it is in the "proper tail call" form.

```sub factorial {
my (\$n, \$accumulator) = @_;
\$accumulator ||= 1;
if (\$n == 0) {
return \$accumulator;
}
return factorial(\$n - 1, \$n * \$accumulator);
}
Most modern optimizing compilers will be able to turn this version into machine code equivalent to the iterative version. Meaning that instead of a call structure like this:
```call factorial ...
call factorial ...
call factorial ...
call factorial ...
return
return
return
return
You end up with something that looks more like this:
```call factorial ...
change args and reloop ...
change args and reloop ...
change args and reloop ...
return
Basically the code becomes this:
```sub factorial {
my (\$n, \$accumulator) = @_;
\$accumulator ||= 1;
LOOP:
if (\$n == 0) {
return \$accumulator;
}
\$accumulator *= \$n;
\$n--;
goto LOOP;
}
Now one problem of course is that perl does not do this type of optimization :)

Standard ML is a functional language, which means that calling functions is important, so therefore, the Standard ML compiler is built to optimize function calls. As for recursion, it uses a heap based allocation rather than stack based, which allows for a number of optimizations to take place. I would provide a link on this, but to be honest, I read it while waist deep in the Standard ML site and I have never been able to dig it out again.

Scheme too makes many optimizations which allow it to be very efficient, even in the face of recusion which would bring most other languages to a halt (since they would have consumed all available resources). Googling "Scheme", "Optimized", etc will get you a number of links to lots of good info.

But my point is that it is unwise, as compiler technology improves, to rule out a recursive solution which is more understandable and maintainable because 5-10 years ago compiler technology couldn't handle it.

There is always a trade off between programmer time (writing, documenting and maintaining) and computer time (execution). Back in the days of yore, computer time was more expensive than programmer time. The inverse is true now.

Once again, it is all in how you use it. Bad recursion is not worse than bad iteration, its all bad programming in the end. If the problem/algorithm itself is recursive then the most understandable and maintainable version of it will be the recursive one.

-stvn

Replies are listed 'Best First'.
Re^5: Behold! The power of recursion.
by audreyt (Hermit) on Oct 19, 2004 at 10:57 UTC
Now one problem of course is that perl does not do this type of optimization :)
Sure, but you can tell it to do that. :-)
```sub factorial {
my (\$n, \$accumulator) = @_;
\$accumulator ||= 1;
if (\$n == 0) {
return \$accumulator;
}
@_ = (\$n - 1, \$n * \$accumulator);
goto &factorial;
}
Ironically, the recursive form (just leave out "goto") is *much* faster. It's a little hard to tell using factorial, but you can see it in this:
```sub rec_max {
return () unless @_;
my (\$h1, \$h2) = (shift, shift);
if (@_) {
unshift @_, (\$h1 > \$h2) ? \$h1 : \$h2;
&rec_max; # Try it with and without goto here
}
elsif (defined \$h2) {
return (\$h1 > \$h2) ? \$h1 : \$h2;
}
}

use List::Util 'shuffle';
print rec_max shuffle(1..2000,1500..3000,3500..8000);
Maybe someone else can explain that.

Caution: Contents may have been coded under pressure.

Indeed!

Benchmark results:

```              Rate uses_goto    normal  uses_amp
uses_goto  94719/s        --      -10%      -14%
normal    105040/s       11%        --       -4%
uses_amp  109823/s       16%        5%        --

Rate uses_goto    normal  uses_amp
uses_goto  94448/s        --       -8%      -14%
normal    103141/s        9%        --       -7%
uses_amp  110408/s       17%        7%        --

Rate uses_goto    normal  uses_amp
uses_goto  94148/s        --      -11%      -14%
normal    105616/s       12%        --       -4%
uses_amp  109985/s       17%        4%        --

Benchmark code:

Create A New User
Node Status?
node history
Node Type: note [id://400188]
help
Chatterbox?
 [marto]: "Eugenie Scott, executive director of the National Center for Science Education, dubbed this approach the Gish gallop, describing it as "where the creationist is allowed to run on for 45 minutes or an hour, spewing forth torrents of error that the [marto]: evolutionist hasn't a prayer of refuting in the format of a debate." She also criticized Gish for failing to answer objections raised by his opponents" [erix]: one would hope evolutionists haven't any prayers anyway [marto]: obviously someone could be religious, but not creationist [erix]: "Nothing in Intelligent Design makes sense except in the light of Creationism" <-- I made that one up myself (free after Dobzhansky )

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (9)
As of 2017-07-28 15:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (431 votes). Check out past polls.