Doesn't OCaml have any recursion checks?

Question

I've been playing with OCaml recently, and promptly did my favourite thing to check how well developed a VM/Compiler really is, and wrote a recursive Program:

let rec f i =
    Printf.eprintf "i = %d\n" i;
    f(i+1);;

let () =
    f 0;;

The program runs as expected, however, the recursion NEVER breaks, infact, I had this program running for some times (roughly 30 minutes), redirected stderr to a File, to avoid clogging up my terminal. After checking the file, I was astounished when I noticed that the file was around 7*GB* big!

How can this be? Doesn't OCaml have any recursion limits?

@Pascal Cuoq: You should post that as answer, so I can accept it ;-) — , Feb 04 '11 at 09:33

score 15 · Accepted Answer · answered Feb 04 '11 at 09:41

You should look for information about tail-call optimization.

To answer your question, there is a stack limit, which would have been reached by your program if the stack was growing.

You shouldn't expect to reach it with your program any more than you would expect a division by zero in a useless expression in a C program to always produce a division by zero once compiled: the compiler might remove the useless division. In your example, the compiler removed the useless stack overflow.

Actually, it goes a bit further than that. As explained on the Wikipedia page, OCaml and most functional languages guarantee that the tail-call transformation is done, so that you can rely on it when using recursion.

And to think of it another way: since recursion is the standard looping construct in functional languages, a recursion limit in OCaml would be equivalent to a limit on how many times a loop can run in C or Python. — Michael Ekstrand, Feb 04 '11 at 20:00
Only if the function is tail recursive, otherwise it will stackoverflow in the exception of a loop — 0xFF, Feb 05 '11 at 20:46

score 4 · Answer 2 · answered Feb 13 '11 at 08:39

Pascal is correct, but I think more explanation is in order because there are limits.

OCaml implements tail call recursion. If the return value of a function is wholly the result of a function call, then the call can be optimized. Consider these two pieces of code:

let rec foo i = 
  i * foo(i-1)

and

let rec bar i j = 
  bar(i - 1, j * i)

These both calculate the the same thing (and neither terminates). However, the first will cause a stack overflow and the 2nd will not. Why? Because foo does a calculation with the result of the function call. This means the value i need to be kept on the stack until foo (i - 1) returns. On the other hand, the result of bar is the result of the call bar (i - 1, j * i) with no modification. There is nothing that has to be kept on the stack.

Visualize it this way. Let's say we start with i = 3 (and j = 1). Foo would look like this:

foo(3)
  3 * foo (2)
    2 * foo (1)

and bar would look like this:

bar (3, 1)
bar (2, 3)
bar (1, 6)

score 0 · Answer 3 · answered Feb 04 '11 at 09:22

0

Caveat, I don't know OCaml, but this is typical of a compiler or VM that implements tail call optimization. In the case of your function above, even the more limited optimization on tail recursion applies.

answered Feb 04 '11 at 09:22

rlibby

5,931
20
25

Doesn't OCaml have any recursion checks?

3 Answers3