Version française
Home     About     Download     Resources     Contact us    
Browse thread
Simple factorial
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Tom <tom.primozic@g...>
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