From: Kent M Pitman
Subject: Re: Urgent: need a tail recursive....decimal to binary source code
Date:
Message-ID: <sfw7lxzqztx.fsf@world.std.com>
·········@hotmail.com (Joe) writes:
> I need source code for a tail recursive program that will convert
> decimal number into binary ..... any help would be most appreciated.
Urgent? Is this a homework assignment? If not, can you say a few
words about what your intended application is?
And what do you mean by "decimal"? (Lisp has no "decimal" datatype.)
Do you mean an integer? A float? This query is underspecified.
From: Lars Magne Ingebrigtsen
Subject: Re: Urgent: need a tail recursive....decimal to binary source code
Date:
Message-ID: <m367dja1yg.fsf@sparky.gnus.org>
Kent M Pitman <······@world.std.com> writes:
> And what do you mean by "decimal"? (Lisp has no "decimal" datatype.)
I'm guessing a string that contains some representation of a base ten
number.
--
(domestic pets only, the antidote for overdose, milk.)
·····@ifi.uio.no * Lars Magne Ingebrigtsen
On Sat, 17 Oct 1998 09:53:30 GMT, Kent M Pitman <······@world.std.com>
wrote:
>·········@hotmail.com (Joe) writes:
>
>> I need source code for a tail recursive program that will convert
>> decimal number into binary ..... any help would be most appreciated.
>
>Urgent? Is this a homework assignment? If not, can you say a few
>words about what your intended application is?
>
>And what do you mean by "decimal"? (Lisp has no "decimal" datatype.)
>Do you mean an integer? A float? This query is underspecified.
>
Yes i do mean an integer!.......the reason why i need this program
is for one of my LAB classes ........ i missed a class because i was
ill and that is the only question that i am stuck on!......it URGENT
because i have to go see my tutor and hand in my LABS.
If you could help me and if you do me one more favor...... explain the
tail recursive difference and how the program is tail recursive, since
i have written the program but it's not tail recursive......so i have
been told.
Any help would be very much appreciated!!!!!!!!!!!!
·········@hotmail.com (Joe) writes:
> Yes i do mean an integer!.......the reason why i need this program
> is for one of my LAB classes ........ i missed a class because i was
> ill and that is the only question that i am stuck on!......it URGENT
> because i have to go see my tutor and hand in my LABS.
Well, giving you the *solution* is certainly out of the question. But I can
tell you about tail recursion.
> If you could help me and if you do me one more favor...... explain the
> tail recursive difference and how the program is tail recursive, since
> i have written the program but it's not tail recursive......so i have
> been told.
>
> Any help would be very much appreciated!!!!!!!!!!!!
There are two ways to implement recursion. Consider factorial:
v1
(defun factorial (n)
(if (= n 0)
1
(* n (factorial (1- n)))))
v2
(defun factorial (n)
(factorial-helper n 1))
(defun factorial-helper (n result)
(if (= n 0)
result
(factorial-helper (1- n) (* n result))))
The difference between v1 and v2 is significant. For each number from 0 to
n, v1 requires a stack frame. It can't be thrown away, otherwise you would
lose part of the result. When you return from your recursive calls, the
result is calculated on the way out. v2 on the other hand keeps the result
on the stack. So, when factorial-helper starts on the next loop for n-1,
the previous stack frame becomes irrelevant. This stack frame can be then
reused. You save space, and the code can also be potentially be more
efficiently executed.
For example:
v1:
(factorial 3)
-> (* 3 (factorial 2))
-> (* 3 (* 2 (factorial 1)))
-> (* 3 (* 2 (* 1 (factorial 0))))
-> (* 3 (* 2 (* 1 1)))
-> (* 3 (* 2 1))
-> (* 3 2)
6
v2:
(factorial 3)
-> (factorial-helper 3 1)
-> (factorial-helper 2 3)
-> (factorial-helper 1 6)
-> (factorial-helper 0 6)
6
Sunil
his email address says it all.
--
Raffael Cavallaro
From: Rahsheen Anthony Porter
Subject: Re: Urgent: need a tail recursive....decimal to binary source code
Date:
Message-ID: <70q47a$cs2$1@solaria.cc.gatech.edu>
Joe (·········@hotmail.com) wrote:
: Any help would be very much appreciated!!!!!!!!!!!!
If you put about 3 more '!'s on that, I think I'll actually be able to
hear you...
--
-Rahsheen Anthony Porter (········@cc.gatech.edu)
From: marisa
Subject: Re: Urgent: need a tail recursive....decimal to binary source code
Date:
Message-ID: <36288A29.C6824340@kabelfoon.nl>
Joe wrote:
> I need source code for a tail recursive program that will convert
> decimal number into binary ..... any help would be most appreciated.
The following code is tail recursive :-)
(setq *print-base* 2)
From: rusty craine
Subject: Re: Urgent: need a tail recursive....decimal to binary source code
Date:
Message-ID: <70blah$8bn$1@excalibur.flash.net>
Joe wrote in message <················@news.latrobe.edu.au>...
>I need source code for a tail recursive program that will convert
>decimal number into binary ..... any help would be most appreciated.
Just in case it's the math you are having trouble with I'll show you how to
do a binary to integer in english........and if it is the math....hit the
books. A programmer without math skills...might as well be a Unix System
Administartor. Our sysadm never sees the light of day, works deep nights,
eats alot of cold pizza, doesn't shave and his name is contantly prefixed
with four letter anglo-saxon words :). (study hard)
rusty
To convert a binary number to a decimal number you must first
understand what each digit in the binary number means. To explain this
let's look at the decimal number 247.
The '2' in 247 represents two hundred because it is a two in the
hundreds position (two times a hundred is two hundred). In similar
fashion, the '4' in 247 represents forty because it is a four in the
tens position (four times ten is forty). Finally, the '7' represents
seven because it is a seven in the units position (seven times one is
seven). In a decimal number, the actual value represented by a digit
in that number is determined by the numeral and the position of the
numeral within the number.
It works the same way with a binary number. The right-most position in
a binary number is units; moving to the left, the next position is
twos; the next is fours; the next is eights; then sixteens; then
thirty-twos ... Notice that these numbers are all powers of two -
2^0, 2^1, 2^2, 2^3, 2^4, 2^5. (The units, tens, hundreds, thousands,
ten thousands of the decimal system are all powers of ten: 10^0, 10^1,
10^2, 10^3, 10^4).
So, to convert the binary number 1001 (don't read that as one thousand
one - read it as one zero zero one) to decimal, you determine the
actual value represented by each '1' and add them together. The
right-most '1' has a decimal value of 1 (it is in the 2^0, or units,
position) and the left-most '1' has a decimal value of 8 (it is in the
2^3, or eights, position). So the binary number 1001 is equal to
decimal 9. Here's another way to look at it: 1 0 0 1 ^ ^ ^ ^
| | | |_________> 1 x 2^0 = 1 x 1 = 1
| | |___________> 0 x 2^1 = 0 x 2 = 0
| |_____________> 0 x 2^2 = 0 x 4 = 0
|_______________> 1 x 2^3 = 1 x 8 = 8
---
9
From: David Steuber "The Interloper
Subject: Re: Urgent: need a tail recursive....decimal to binary source code
Date:
Message-ID: <362c3f0f.2535075@news.newsguy.com>
On Sat, 17 Oct 1998 21:57:02 -0500, "rusty craine"
<········@flash.net> claimed or asked:
% Just in case it's the math you are having trouble with I'll show you how to
% do a binary to integer in english........and if it is the math....hit the
% books. A programmer without math skills...might as well be a Unix System
% Administartor. Our sysadm never sees the light of day, works deep nights,
% eats alot of cold pizza, doesn't shave and his name is contantly prefixed
% with four letter anglo-saxon words :). (study hard)
You could have saved yourself a lot of effort by just pointing out
that Knuth's "The Art of Programming" vol 3, Semi-numerical algorithms
contains a procedure for arbitrary radix conversion. Mix, anyone?
"A system admin's life is a sorry one. The only advantage he has over
Emergency Room doctors is that malpractice suits are rare. On the
other hand, ER doctors never have to deal with patients installing new
versions of their own innards!" --- Michael O'Brien
--
David Steuber (ver 1.31.2a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.
So I have this chicken, see? And it hatched from this egg, see? But
the egg wasn't laid by a chicken. It was cross-laid by a turkey.