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/c... 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)

on 2009-02-11 02:16

on 2009-02-11 02:40

Li Chen <removed_email_address@domain.invalid> writes: > > 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.

on 2009-02-11 03:05

Li Chen wrote: > Thanks, > if dec==0 ||dec==1 > results<<1 if dec==1# if number is 2 > 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

on 2009-02-11 03:33

William J. 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

on 2009-02-11 03:45

On Tue, Feb 10, 2009 at 5:32 PM, Li Chen <removed_email_address@domain.invalid> wrote: > > 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.

on 2009-02-11 03:47

William J. 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

on 2009-02-11 05:15

"William J." <removed_email_address@domain.invalid> 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.

on 2009-02-11 09:45

Li Chen wrote: > > result.reverse.join "" > > 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 = [] ^^^^

on 2009-02-11 09:51

Li Chen wrote: > > 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.

on 2009-02-11 10:10

Pascal J. Bourguignon wrote: > "William J." <removed_email_address@domain.invalid> 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.

on 2009-02-11 11:51

Li Chen <removed_email_address@domain.invalid> writes: >> result.reverse.join "" > > 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).

on 2009-02-11 16:50

Pascal J. Bourguignon wrote: > 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). Hi Pascal, Thanks for the explanation. But I wonder which page in the PickAxe mentions about this kind of usage? Li

on 2009-02-11 17:08

On Wed, 2009-02-11 at 09:15 +0900, 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/c... > > But my codes don't work. Any idea or optimization? The main idea behind recursion is that we break a problem into a representation of the same problem. In this case, we are taking a number, n. We want the value of that n, modulo 2, + the binary value of (n / 2). Using that approach, for 4, we'd get: (n%2) + ((n/2)%2) + ((n/2)/2)%2 which is "001" -- the reverse of what we were wanting. However, if we turn it around, we can say that the binary representation of n is equivalent to: the binary representation of (n/2) + (n modulo 2) Or, if you will: def decimal_to_binary(num = 0) ((num > 1) ? decimal_to_binary(num / 2) : "") + (num % 2).to_s end No arrays needed, nor any reversing. We could also have written it as: def decimal_to_binary(num = 0) if (num > 1) then results = decimal_to_binary(num/2) else results = "" end results + (num % 2).to_s end So, were we to call it with 4, the following calls to decimal_to_binary would happen: decimal_to_binary(4) (which returns the next line + "0") decimal_to_binary(2) (which returns the next line + "0") decimal_to_binary(1) (which returns "1") or, if you will, "100" I'm sure there's probably ways to optimize my code even more, but it works..... Matt

on 2009-02-11 18:35

Matthew W. wrote: >> The main idea behind recursion is that we break a problem into a > representation of the same problem. In this case, we are taking a > number, n. We want the value of that n, modulo 2, + the binary value of > (n / 2). > > Using that approach, for 4, we'd get: > > (n%2) + ((n/2)%2) + ((n/2)/2)%2 > > which is "001" -- the reverse of what we were wanting. However, if we > turn it around, we can say that the binary representation of n is > equivalent to: > > the binary representation of (n/2) + (n modulo 2) Hi Matt, Thank you very much. Your explanation is so sweet! Li