Re: [Caml-list] Simple factorial

[Tom <tom.primozic@gmail.com>]

[-- 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 --]