What is the difference between these two recursive ocaml functions?

Question

let rec x1() = x1();()
let rec x2() = x2();;

Calling x1();; generates a stack overflow whereas calling x2();; causes the program to run indefinitely. What is the difference between the 2 functions?

Answer 1

let rec x1() = x1();()

This function is not tail recursive. It calls itself x1(); and when this call returns, the function will return a unit ().

let rec x2() = x2();;

This function is calling itself at the very end; therefore the compiler can perform tail-call optimization - which will mean that the recursive function calls will never use up all the stack space.

This page explains tail recursion: http://ocaml.org/learn/tutorials/if_statements_loops_and_recursion.html#Tailrecursion - It is a fundamental technique used by functional programming languages so that we can use recursion for implementing loops without running out of memory.

I first learnt about the process stack when I read Smashing The Stack For Fun And Profit; I still think that it has the best description of what the process stack is all about.