Hi,
To give you a hint without actually solving the original problem, which
is your task, and perhaps confuse you a little bit more, here's a
definition of tail-recursive Factorial that given an non-negative
integer N returns the list of successive factorials from in increasing
order from 0! to N!, i.e., [0! 1! ... N!]:
declare
Factorial =
local
fun {Factorial N I Head Tail Last}
if I>N
then Tail=nil Head
else NewLast=I*Last NewTail in
Tail=NewLast|NewTail
{Factorial N I+1 Head NewTail NewLast} end end
Tail in
fun {$ N}
if N==0
then [1]
else {Factorial N 1 1|Tail Tail 1} end end end
{Browse {Factorial 5}}
% [1 1 2 6 24 120]
(pardon me the idiosyncratic formatting).
vQ
On 09/29/2010 06:57 PM, Peter Breitsprecher wrote:
Raphael, Lyle,
Thank you for the responses, and Lyle, I did play with it for quite a
while before I looked at your code.... My code didn't give me the
right result, it didn't create a list, or it didn't run. However when
I looked at Lyle's code, it was similar to mine, only he had an extra
value that I wasn't using(which could have been why it wasn't working
for me. Then I looked at lyles code put in in Oz, and it doesn't give
me the desired result either. When it runs(and when I stepped through
it it seemed logical), it gave me the result [6 2 1 1].
So then instead of if I==N then Acc, I tried every other combination I
thought would work, I started Acc at nil, but that obviously didn't
work, then I tried I==N+1 which gives me the proper end result in 24,
but the list looks like [24 6 2 1 1].
I'm a little confused as to where the extra value comes from. I can
only assume that it is from when we initalize the list in the {Fact N}
Function because it starts Acc as [1]. So I assume it takes that 1
puts it in there then multiplies it by one and then puts the second
one in after the first pass. I must be able to initialize Acc to nil
and make if I==N then 1, but it doesn't seem to work.
I thought this should be way easier than it has been... and then we go
from this assignment to creating a French Parser, and out Project is a
Scheme Interpreter.... My head was spinning as it is before this....
Dear Peter,
It is indeed possible to turn the factorial list function into a tail
recursive one.
Think about how to build the list with an accumulator, such that
the final
result is the last value of the accumulator. Each element of the list
depends on the element that comes next, therefore you should build
the list
from right to left. Successive values of the accumulator should be:
[1]
[2 1] = 2|[1]
[6 2 1] = 6|[2 1]
[24 6 2 1] = 24|[6 2 1]
Consider you loop over an index going from 1 to N, and you should
be able to
write a tail recursive function that uses the accumulator as I
described
above, and returns the expected list at the end.
Good luck :-)
Raphael
On Wed, Sep 29, 2010 at 6:44 PM, Peter Breitsprecher
<[email protected] <mailto:[email protected]>>wrote:
> Ok I admit It I am stumped. I know I'm new to this Language,
but I'm
> trying and want to learn. We were given this code.
>
> fun {Fact N}
> if N==1 then [N]
> else
> Out={Fact N-1}
> in
> N*Out.1|Out
> end
> end
>
> Example of execution: {Fact 4} -> [24 6 2 1]
>
> He asked if this program is tail recursive, which it is not,
because the
> recursion needs to be the last operation, and in this case the last
> operation is the N*Out.1.
>
> So I wrote these two pieces of code.
>
> This one you need to pass the Accumulator to in the function call
>
> fun {Fact N Acc}
> if N==1 then Acc
> else
> {Fact N-1 N*Acc}
> end
> end
>
> And this one that uses another function to loop.
>
> fun {Fact N}
> fun {FactLoop N Acc}
> if N == 0 then Acc
> else
> {FactLoop N-1 N*Acc}
> end
> end
> in
> {FactLoop N 1}
> end
>
> Now my problem is that I get the end result of 24 with these
programs, but
> I can't get them to display a list like in the example the
professor gave
> us.
>
> How do I change my code, or make the Professor code so that it
is tail
> recursive and still produce a list. In Part B of the question
it is to
> order the list of factorials from smallest to largest, which I
have finished
> using his code, but not tail recursive.
>
> Also, can someone please tell me how to reply to these threads? I am
> submitting my responses Via Email, but they don't seem to end up
here.
>
> Thank you for your help.
>
>
>
> --
> Kurt Breitsprecher
> (807) 474-9601
> [email protected] <mailto:[email protected]>
>
>
>
>
_________________________________________________________________________________
> mozart-users mailing list
> [email protected] <mailto:[email protected]>
> http://www.mozart-oz.org/mailman/listinfo/mozart-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://lists.gforge.info.ucl.ac.be/pipermail/mozart-users/attachments/20100929/a73653b9/attachment-0001.html
------------------------------
Message: 4
Date: Wed, 29 Sep 2010 14:26:22 -0700
From: Lyle Kopnicky <[email protected] <mailto:[email protected]>>
Subject: Re: Recursive Tail Factorial
To: Mozart users <[email protected] <mailto:[email protected]>>
Message-ID:
<[email protected]
<mailto:[email protected]>>
Content-Type: text/plain; charset="iso-8859-1"
Hi Peter,
When accumulating you will still have to do the multiplications in
the same
order. If you want to accumulate a list of the intermediate steps, you
cannot start with the bigger numbers and multiply down to the smaller
numbers. The recursion is masking the fact that the smaller
numbers are
really getting multiplied first.
So, you should count up in your accumulator rather than down. Here's a
solution:
fun {FactLoop I N Acc}
if I==N
then Acc
else {FactLoop I+1 N I*Acc.1|Acc}
end
fun {Fact N}
{FactLoop 1 N [1]}
end
Your accumulator starts with the smallest value of 1, and you
count up until
you reach the biggest value.
- Lyle
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://lists.gforge.info.ucl.ac.be/pipermail/mozart-users/attachments/20100929/ec22af21/attachment.html
------------------------------
_______________________________________________
mozart-users mailing list
[email protected] <mailto:[email protected]>
http://lists.gforge.info.ucl.ac.be/mailman/listinfo/mozart-users
End of mozart-users Digest, Vol 46, Issue 26
********************************************
--
Kurt Breitsprecher
(807) 474-9601
[email protected] <mailto:[email protected]>
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
