note
fullermd
<blockquote><p>
I naively expect above/below above/below above/below return sequence, rather than above/above/above below/below/below return.
</p></blockquote>
<code>
print "above\n";
my $E = binary($k);
print "below\n";
</code>
<p>
No, it has to finish the <c>binary($k)</c> before it can do the <c>print "below\n"</c>. And that <c>binary()</c> call has its own <c>above/binary()/below</c> sequence to follow. It would be like saying:
</p>
<code>
print "x\n";
print "y\n";
print "z\n";
</code>
<p>
You wouldn't expect that to output "x/z/y", would you? Each line has to finish before the next one starts, and the recursive <c>binary()</c> call will (from the top) also involve another recursive call before it returns to the original call.
</p>
<p>
It may be simpler to look a version without the calculations, just showing the call path:
</p>
<code>
# How many steps we want to take
my $steps = 3;
sub recur
{
my ($x) = @_;
# Create a number of leading spaces equal to our current $x
my $ldr = " " x $x;
# Note that we're starting
print "${ldr}Start with $x\n";
# We only go to $steps to make it a smallish example
if($x >= $steps)
{
print "${ldr}At $steps, returning.\n";
return;
}
# Recurse with the next number. Say we're doing it, do it, say we're
# done.
my $y = $x + 1;
print "${ldr}-> Subcall with $y\n";
recur($y);
print "${ldr}<- Back from $y\n";
# And now we're done with this number, so step back
print "${ldr}Done with $x\n";
}
# Start off
recur(0);
</code>
<p>
So now we're just calling ourselves <c>$steps</c> times, and noting where we go. Output:
</p>
<code>
% ./tst.pl
Start with 0
-> Subcall with 1
Start with 1
-> Subcall with 2
Start with 2
-> Subcall with 3
Start with 3
At 3, returning.
<- Back from 3
Done with 2
<- Back from 2
Done with 1
<- Back from 1
Done with 0
</code>
<p>
So what happens? We start off by calling <c>recur()</c> with 0. So that says it's doing so, then re-calls itself with 1. That says it's doing so, re-calls with 2. Says it's doing so, re-calls with 3.
</p>
<p>
Now the 3 notices that's our limit, and so it returns. It returns back to the re-call that had 2, which now completes, and returns. It returns back to the re-call that had 1, which now completes, and returns. It returns back to the original call with 0, which returns. And then it falls off the end of the script.
</p>
1131563
1131563