Asp Forum - how to do the recursion

Li Chen

2/11/2009 12:15:00 AM

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/decimal2b...

But my codes don't work. Any idea or optimization?

Thanks,

Li

###############
def decimal_to_binary(number)

dec=number
results=[]

if dec==0 ||dec==1
results<< dec
else

mode=dec%2
if mode==1# this is an odd number
results<<1
dec=(dec-1)/2
elsif mode==0 #this is an even number
results<<0
dec=dec/2
results<<1 if dec==1# if number is 2
end
end

decimal_to_binary(dec) if dec>1
p results.reverse

end

##############
decimal_to_binary(3)
--
Posted via http://www.ruby-....

14 Answers

pjb

2/11/2009 12:40:00 AM

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/demal2b...
>
> 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__

William James

2/11/2009 12:59:00 AM

Li Chen wrote:

> 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/de...
> ry.html
>
> But my codes don't work. Any idea or optimization?
>
> Thanks,
>
> Li
>
>
> ###############
> def decimal_to_binary(number)
>
> dec=number
> results=[]
>
> if dec==0 ||dec==1
> results<< dec
> else
>
> mode=dec%2
> if mode==1# this is an odd number
> results<<1
> dec=(dec-1)/2
> elsif mode==0 #this is an even number
> results<<0
> dec=dec/2
> results<<1 if dec==1# if number is 2
> end
> end
>
> decimal_to_binary(dec) if dec>1
> p results.reverse
>
> end
>
>
> ##############
> decimal_to_binary(3)

If you found Pascal's code somewhat puzzling, let me explain.
His customary language is CLisp, so when he deigns to dabble
in Ruby, he tries to make his code look lispish.

def dec_to_binary num, result = []
result <<
if num.odd?
1
else
0
end
if num < 2
result.reverse.join ""
else
dec_to_binary num/2, result
end
end

p dec_to_binary 254

Li Chen

2/11/2009 1:32:00 AM

William James wrote:

>> If you found Pascal's code somewhat puzzling, let me explain.
> His customary language is CLisp, so when he deigns to dabble
> in Ruby, he tries to make his code look lispish.

Hi Will,

Thank you for your rubyish code.

Yes. I am really confused when I read Pascal's codes. I don't think
nowhere in Pixaxe ever mentions about function BUT only methods and
objects!

I have questions about two code lines:
1) result <<

What does it mean, concatenate nothing???

2) num.odd?
When I run the code Ruby complains about #odd?. I check the class Fixnum
and I can't find #odd? So I change it to num%2==1 and Ruby runs happily.

Thanks,

Li

>
> def dec_to_binary num, result = []
> result <<
> if num.odd?
> 1
> else
> 0
> end
> if num < 2
> result.reverse.join ""
> else
> dec_to_binary num/2, result
> end
> end
>
>
> p dec_to_binary 254

--
Posted via http://www.ruby-....

Christopher Dicely

2/11/2009 1:43:00 AM

On Tue, Feb 10, 2009 at 5:32 PM, Li Chen <chen_li3@yahoo.com> wrote:
> William James wrote:
>
>>> If you found Pascal's code somewhat puzzling, let me explain.
>> His customary language is CLisp, so when he deigns to dabble
>> in Ruby, he tries to make his code look lispish.
>
>
> Hi Will,
>
> Thank you for your rubyish code.
>
> Yes. I am really confused when I read Pascal's codes. I don't think
> nowhere in Pixaxe ever mentions about function BUT only methods and
> objects!

Ruby doesn't really have "functions", as such, but methods of the
current object look and act (mostly) like functions in other
languages.

Li Chen

2/11/2009 1:46:00 AM

William James wrote:

> def dec_to_binary num, result = []
> result <<
> if num.odd?
> 1
> else
> 0
> end
> if num < 2
> result.reverse.join ""
> else
> dec_to_binary num/2, result
> end
> end
>
>
> p dec_to_binary 254

Hi Will,

I have one more question about the method call:

When you define method dec_to_binary, you pass two parameters.
But when you call the method, you only provide one parameter.

Surprisingly Ruby doesn't complain it. How to explain this seemly
inconsistancy?

Thanks,

Li

--
Posted via http://www.ruby-....

pjb

2/11/2009 3:14:00 AM

"William James" <w_a_x_man@yahoo.com> writes:
> If you found Pascal's code somewhat puzzling, let me explain.
> His customary language is CLisp, so when he deigns to dabble
> in Ruby, he tries to make his code look lispish.

Indeed. But at least, I write _ruby_ code in c.l.r.

--
__Pascal Bourguignon__

William James

2/11/2009 7:43:00 AM

Li Chen wrote:

> William James wrote:
>
> > def dec_to_binary num, result = []
> > result <<
> > if num.odd?
> > 1
> > else
> > 0
> > end
> > if num < 2
> > result.reverse.join ""
> > else
> > dec_to_binary num/2, result
> > end
> > end
> >
> >
> > p dec_to_binary 254
>
>
> Hi Will,
>
> I have one more question about the method call:
>
> When you define method dec_to_binary, you pass two parameters.
> But when you call the method, you only provide one parameter.
>
> Surprisingly Ruby doesn't complain it. How to explain this seemly
> inconsistancy?
>
> Thanks,
>
> Li

I told dec_to_binary to use the default value [] for result
when no value for result is passed to the function:

def dec_to_binary num, result = []
^^^^

William James

2/11/2009 7:47:00 AM

Li Chen wrote:

> William James wrote:
>
> >> If you found Pascal's code somewhat puzzling, let me explain.
> > His customary language is CLisp, so when he deigns to dabble
> > in Ruby, he tries to make his code look lispish.
>
>
> Hi Will,
>
> Thank you for your rubyish code.
>
> Yes. I am really confused when I read Pascal's codes. I don't think
> nowhere in Pixaxe ever mentions about function BUT only methods and
> objects!
>
> I have questions about two code lines:
> 1) result <<
>
> What does it mean, concatenate nothing???

That line is not complete by itself. The following lines provide
either 1 or 0 to be concatenated.

>
> 2) num.odd?
> When I run the code Ruby complains about #odd?. I check the class
> Fixnum and I can't find #odd? So I change it to num%2==1 and Ruby
> runs happily.

It works with ruby 1.8.7 (2008-05-31 patchlevel 0). You may have an
older version.

>
>
> Thanks,
>
> Li
>
>
> >
> > def dec_to_binary num, result = []
> > result <<
> > if num.odd?
> > 1
> > else
> > 0
> > end
> > if num < 2
> > result.reverse.join ""
> > else
> > dec_to_binary num/2, result
> > end
> > end
> >
> >
> > p dec_to_binary 254

--

William James

2/11/2009 8:05:00 AM

Pascal J. Bourguignon wrote:

> "William James" <w_a_x_man@yahoo.com> writes:
> > If you found Pascal's code somewhat puzzling, let me explain.
> > His customary language is CLisp, so when he deigns to dabble
> > in Ruby, he tries to make his code look lispish.
>
> Indeed. But at least, I write ruby code in c.l.r.

Don't hesitate to post Commune Lisp solutions to problems presented
here. That will help everyone appreciate how good Ruby is.

pjb

2/11/2009 9:46:00 AM

Li Chen <chen_li3@yahoo.com> writes:

> William James wrote:
>
>> def dec_to_binary num, result = []
>> result <<
>> if num.odd?
>> 1
>> else
>> 0
>> end
>> if num < 2
>> result.reverse.join ""
>> else
>> dec_to_binary num/2, result
>> end
>> end
>>
>>
>> p dec_to_binary 254
>
>
> Hi Will,
>
> I have one more question about the method call:
>
> When you define method dec_to_binary, you pass two parameters.
> But when you call the method, you only provide one parameter.
>
> Surprisingly Ruby doesn't complain it. How to explain this seemly
> inconsistancy?

That's possible because we specified a default value of some of these parameters.
William specified an empty array as the default for result: result = []
I specified an empty string: result=""
That renders the corresponding argument optional.

(Of course, all the parameters with defaults must be last in the
paramater list, and the optional arguments are assigned in order).

--
__Pascal Bourguignon__

comp.lang.ruby

how to do the recursion

Li Chen

pjb

William James

Li Chen

Christopher Dicely

Li Chen

pjb

William James

William James

William James

pjb

x Login to ForumsZone