From: pjb@... (Pascal J. Bourguignon)
Date: 2009-02-11T09:38:58+09:00
Subject: Re: how to do the recursion

Li Chen <chen_li3@yahoo.com> writes:

> Hi all,
>
> In order to study recursion, I want to change a decimal number into a
> binary number  based on the algorithm on website
>
> http://www.trunix.org/programlama/cpp/fred/notes/cpp/misc/demal2binary.html
>
> But my codes don't work. Any idea or optimization?
>
> Thanks,
>
> Li
>
>
> ###############
> def decimal_to_binary(number)
>
>    dec=number
>    results=[]

This is a local variable.  It won't cross recursive call boundaries!


You've got (at least) three choices:


- make a pure function, but you may need to further process the
  result, thus not making tail calls (but it may not matter in Ruby, I
  don't know if TCO is implemented here, I'd bet no).

     (def decimal_to_binary(number)
        (if (number < 2)
           (number . to_s)
         else
           ((decimal_to_binary (number / 2)) + ((number % 2) . to_s))
         end)
      end)


- pass an argument that is modified (but it's not a pure function
  anymore).  In this case, to avoid an auxiliary function, we can
  profit from the default value for the additionnal argument, (but
  this is not pretty since it would allow a client to give an
  inconsistent initial value).

     (def decimal_to_binary(number,result="")
        (result . concat((number % 2) . to_s))
        (if (number > 1)
           (decimal_to_binary((number / 2),result))
         end)
        (result . reverse)
      end)
     
         
- use an accumulator pattern, passing the result so far to the
  recursive tail calls.

     (def decimal_to_binary(number,result="")
        (if (number < 2)
           ((number . to_s) + result)
         else
            (decimal_to_binary (number / 2),(((number % 2) . to_s) + result))
         end)
     end)


Compare:
    (begin
      (a = "Hello")
      (decimal_to_binary 42,a)
      a
    end)
with the last two solutions.


-- 
__Pascal Bourguignon__