Factorial function

Factorial function

[Lucas Holland]

Hi, why does this function:

let rec fact n =
	n * fact (n-1);;

yield an overflow error if called with n = 5?

Thanks in advance,

Lucas

RE: [Caml-list] Factorial function

[Steve Taylor]

This function does not terminate where you think it does.  What is your base case?

> -----Original Message-----
> From: caml-list-bounces@yquem.inria.fr [mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of
> Lucas Holland
> Sent: Tuesday, January 23, 2007 10:54 AM
> To: caml-list@inria.fr
> Subject: [Caml-list] Factorial function
> 
> Hi, why does this function:
> 
> let rec fact n =
> 	n * fact (n-1);;
> 
> yield an overflow error if called with n = 5?
> 
> Thanks in advance,
> 
> Lucas
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Factorial function

[William D. Neumann]

On Tue, 23 Jan 2007, Lucas Holland wrote:

> Hi, why does this function:
>
> let rec fact n =
> 	n * fact (n-1);;
>
> yield an overflow error if called with n = 5?

It overflows because you don't provide a base case for the recursion (e.g. 
if n = 1 then 1 else ...), it simply cycles backwards through the ints 
until the stack is exhausted.

Also, if you're just learning OCaml, you may want to use the Caml 
Beginners list for these types of questions.  You con find the list 
information at: http://groups.yahoo.com/group/ocaml_beginners

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers.  We don't need them, we're not doing 
anything with them.

Tigers are noble and sleek; children are loud and messy."

         -- Neko Case

Life is unfair.  Kill yourself or get over it.
 	-- Black Box Recorder

Re: [Caml-list] Factorial function

[Jonathan Roewen]

Recursive call to fact is not in tail position. And by overflow, you
mean stack overflow.

If fact was in tail position, it would loop forever (since there is no
base case).

You can observe that fact is indeed not in tail position be rewriting
the expression without the infix multiplication.

( * ) n (fact (n-1)

or:
let mul x y = x * y => mul n (fact (n-1))

Anyways, questions like these are better addressed to the beginners
list at yahoo groups.

Jonathan

On 1/24/07, Lucas Holland <hollandlucas@gmail.com> wrote:
> Hi, why does this function:
>
> let rec fact n =
>        n * fact (n-1);;
>
> yield an overflow error if called with n = 5?
>
> Thanks in advance,
>
> Lucas
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>