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