Ahh ... recursion!
Ahh ... recursion
Ahh ... recursio
Ahh ... recursi
...
Sounds like you need to focus on recursion right now
instead of permutations. Forgive me for dodging the
original question, but since the Cookbook really covers this better than i can, i hope my new problem will shed
some favorable light. Contemplate this:
use strict;
eat('Ahh ... recursion!');
sub eat {
my $food = shift;
if ($food) {
print "$food\n";
eat (substr($food,0,length($food)-1));
}
else {
# base case
return;
}
}
First, we call the function with a value. Inside this
function we check to see if $food is true.
Since $food is 'Ahh ... recursion!', it is indeed true, so
we print it and call the function again with a new value -
the orginal value minus the last character. This continues
on and on and on and on until there are no characters left
in the variable $food. When we have exhausted $food, the
else 'kicks in' and we return - without this, we
would be caught in an infinite loop. Well, not really.
Because Perl returns (a false value in this example) by
default, we don't have to worry about explicitly returning (for this example). You can safely remove the else
and it's block, but if you remove the if, the
program will loop infinitely.
So, how does this work? Every time you call a subroutine,
something has to preserve the arguments you have passed to it.
This is implemented internally via a stack.
A stack is simply a list that is accessed
first-in first-out oops, LAST-in first
out (thanks Albannach!), just like a stack of plates at the
all-you-can-eat bar. Each call to the function eat()
places the argument list on the stack - when the base
case (i.e. $food is false) is finally reached, the
stack is unwound. Consider this now, the same example using
an explicit stack:
use strict;
my @stack = ('Ahh ... recursion!');
eat() while @stack;
sub eat {
my $food = pop @stack;
if ($food) {
print "$food\n";
push @stack, substr($food,0,length($food)-1);
}
}
Very similar, but not the same. First, we define the stack
with one element: 'Ahh ... recursion!'. Next we call the
function eat in a while loop: we eat() until @stack is
false (and a false array is one that has no elements).
Inside the function eat(), we first pop the first element
out of @stack and store this value in $food. Next we check to see if $food is true (AKA,
is not empty). If it is true, we print it, remove the last
character, and push back on @stack. This continues until
we have removed all the characters - effectively
'eating' the string up. When the string $food is only
one character long, we push the result of the final substr
(an empty string) onto @stack. Now the while loop fails,
and the program ends.
I really hope this helps, because personally, recursion
is tough. As a final note, try to understand this program -
the Fibonacci sequence (hint - google Fibonacci sequence
to learn more):
use strict;
my $numb = shift || 20;
print fib($numb), "\n";
sub fib {
my $n = shift;
return 1 if $n < 2;
return fib($n - 2) + fib($n - 1);
}
UPDATE:
Anony is correct - a better test would have been:
if (length $food) ...
# instead of
if ($food) ...
jeffa
L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)
| 