The thing about recursion is, (and this is what trips up most learners) it does NOT compute results UNTIL it has reached the terminating condition. That is, it would go on accumulating non-computed results and builds the final value once it reaches the end of the recursion condition.

Now, it should be seen that for recursion to happen - it always needs two factors in place:

• The means to compute the next thunk (this is what some people call a non-computed result, particularly in Functional Programming communities). This should already be given, it's just the same function - binary above.
• The terminating condition. In the case of binary - the subroutine would just keep chipping down the number until there's nothing left. If it reaches that stage, all it has to do is prepend all previous results. 0 0 1, worked backwards would become 1 0 0 and you have your answer.

Hopefully, I can make this clear by using a well known factorial example.

sub factorial {
  my ($n) = shift;
  if ($n < 2) {
    return 1;
  } else {
    return $n * factorial($n - 1);
  }
}
[download]

Now, consider what would happen if you were to invoke it as: factorial(5). You have the terminating condition and the means to compute the next thunk. It should look something like below:

factorial(5)
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1
= 120

Understood so far? Let's take a look at binary:

• There are 3 variables here: The number itself, the chipped off previous number ($k) and the bit value of that number ($b - this is just what we would get if we divide by 2 and see the remainder - you could simply do $k % 2).
• Is the number broken down completely such that there's no more left? $n == 0 || $n == 1?. if so, just return 1. (It'll never reach down to 0, hopefully :-)
• So, there's more to this number - let's compute its bit value and create our thunk: $E = binary($k). We pass in our chipped down number.
• Ah, so we reached the terminating condition. Finally, we have our value result, not a thunk! Great - let's now prepend all our results back in with so many of these thunks: return $E. $b;. So they all become: 0 0 1 --> 1 0 0

Hopefully, it's all a bit more clear now. You can read more about recursion on Wikipedia here.