This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Simple factorial
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-01-23 (20:31) From: Tom Subject: Re: [Caml-list] Simple factorial
```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

```