I naively expect above/below above/below above/below return sequence, rather than above/above/above below/below/below return.

  print "above\n";
  my $E = binary($k);
  print "below\n";
[download]

No, it has to finish the binary($k) before it can do the print "below\n". And that binary() call has its own above/binary()/below sequence to follow. It would be like saying:

  print "x\n";
  print "y\n";
  print "z\n";
[download]

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 binary() call will (from the top) also involve another recursive call before it returns to the original call.

It may be simpler to look a version without the calculations, just showing the call path:

# 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);
[download]

So now we're just calling ourselves $steps times, and noting where we go. Output:

% ./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
[download]

So what happens? We start off by calling recur() 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.

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.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.