Hello wrinkles,

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.

---

---

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.