Simple factorial

Simple factorial

[Lucas Holland]

Hello,

I've just started learning O'Caml. I've written a simple factorial  
function (no checking whether n is 1 etc.):

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

When I call this function with let's say 5 as an argument, I get an  
overflow error message.

Any ideas?

chell

Re: [Caml-list] Simple factorial

[Tom]

[-- Attachment #1: Type: text/plain, Size: 1332 bytes --]

On 23/01/07, Lucas Holland <hollandlucas@gmail.com> wrote:
>
> Hello,
>
> I've just started learning O'Caml. I've written a simple factorial
> function (no checking whether n is 1 etc.):
>
> let rec factorial n =
>         n * factorial (n-1);;
>
> When I call this function with let's say 5 as an argument, I get an
> overflow error message.
>
> Any ideas?
>

Well... the problem is, that your function "never ends" - the multiplication
continues into infinity. When you make a call
       factorial 5
what actually happens is
       5 * factorial (5-1)
       5 * factorial 4
       5 * 4 * factorial 3
       5 * 4 * 3 * factorial 2
       5 * 4 * 3 * 2 * factorial 1
       5 * 4 * 3 * 2 * 1 * factorial 0
       5 * 4 * 3 * 2 * 1 * 0 * factorial (-1)
       5 * 4 * 3 * 2 * 1 * 0 * (-1) * factorial (-2)
       5 * 4 * 3 * 2 * 1 * 0 * (-1) * (-2) * factorial (-3)
            .
            .
            .
and your function never returns. Checking if n is 1 (or 0) isn't just
neccessary because of the matematical definition of the factorial, but also
because of algorithmic implementation.

The overflow exception you get is generated when a lot of functions are
called (usually this happens in non-tail-recursive list functions with very
big input lists) but don't return, and so they consume all the stack
available.

- Tom

[-- Attachment #2: Type: text/html, Size: 2232 bytes --]

Re: [Caml-list] Simple factorial

[robert]

> I've just started learning O'Caml. I've written a simple factorial
> function (no checking whether n is 1 etc.):
>
> let rec factorial n =
> 	n * factorial (n-1);;
>
> When I call this function with let's say 5 as an argument, I get an
> overflow error message.
>
> Any ideas?
>
You haven't defined a stop condition, so it's going down and down into the
negatives until it overflows.

~~ Robert.

Re: [Caml-list] Simple factorial

[Dário Abdulrehman]

[-- Attachment #1: Type: text/plain, Size: 933 bytes --]

Hi,

Join http://tech.groups.yahoo.com/group/ocaml_beginners/ .
The yahoo list is more appropriate for beginner questions (I am a beginner
too).

Anyway, whatever the programming language you are using, you need to define
a base case for recursion...



On 1/23/07, Lucas Holland <hollandlucas@gmail.com> wrote:
>
> Hello,
>
> I've just started learning O'Caml. I've written a simple factorial
> function (no checking whether n is 1 etc.):
>
> let rec factorial n =
>         n * factorial (n-1);;
>
> When I call this function with let's say 5 as an argument, I get an
> overflow error message.
>
> Any ideas?
>
> chell
>
> _______________________________________________
> 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
>

[-- Attachment #2: Type: text/html, Size: 1602 bytes --]

Re: [Caml-list] Simple factorial

[Till Varoquaux]

Well that's quite a basic error you've got here:
You are making an induction without a base case

a correct implementation of factorial could be:

 let rec factorial= function
  | 0 -> 1
  | n -> n*factorial(n-1);;

This implementation is suboptimal (not tail recursive etc...) but
should be good enough for a beginner.

And since we brought this up, you might want to ask those questions on
the OCaml Beginners list (ocaml_beginners@yahoogroups.com). It seems a
more appropriate place. I also believe some googling could have helped
you, for instance
(http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html)
covers this topic more in depth.

Cheers,
Till

On 1/23/07, Lucas Holland <hollandlucas@gmail.com> wrote:
> Hello,
>
> I've just started learning O'Caml. I've written a simple factorial
> function (no checking whether n is 1 etc.):
>
> let rec factorial n =
>         n * factorial (n-1);;
>
> When I call this function with let's say 5 as an argument, I get an
> overflow error message.
>
> Any ideas?
>
> chell
>
> _______________________________________________
> 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
>