Dermot wrote:
>Hi,
>
>I was reading Higher Order Perl[1] last night and, dishearteningly,
>got stuck on chapter one.
>
>Mark Dominus offers the following as a binary string conversion
>example of how recursion can work.
>
>
>use strict;
>use warnings;
>
>my $bstr = binary(37);
>print "$bstr\n"; # prints 100101
>
>sub binary {
> my ($n) = @_;
> return $n if $n == 0 || $n == 1;
> my $k = int($n/2);
> my $b = $n % 2;
> my $E = binary($k);
> return $E . $b;
>}
>
>
>The algorithm works perfectly but my understanding of it's workings is amiss.
>
>When I look at this I see $E initialised and then concatenate with the
>the modulus of
>37 % 2 =1
>18 % 2 = 0
>9 % 2 = 1
>4 % 2 = 0
>2 % 2 = 0
>
>That by my reckoning is 10100. Almost the reverse of the answer but I
>am obviously wrong and I can't see how the final expressions:
>
>my $E = binary($k);
>return $E . $b;
>
>work to give the answer.
>
>Can someone more enlightened than me give me some guidence.
>Thanx,
>Dp.
Maybe this will make it easier to understand.
On each call 'binary' $b is set as follows (but does not start returning values
until the 6th call):
1. $b = 1 (37 % 2)
2. $b = 0 (18 % 2)
3. $b = 1 (9 % 2)
4. $b = 0 (4 % 0)
5. $b = 0 (2 % 0)
6. returns 1 immediately
Now the stack starts unwinding and appending the $b value to the return value:
5. returns '10' (1 from 6th call and 0 from b value on 5th call).
4. returns '100'
3. returns '1001'
2. returns '10010'
1. returns '100101'
Ken
_________________________________________________________________
Windows Live™: Keep your life in sync.
http://windowslive.com/explore?ocid=TXT_TAGLM_WL_BR_life_in_synch_062009
