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?
Function in ocaml is a expression. That means, a function is a value that represents the function. This is also called anonymous function, lambda. (* syntax for a function expression *) fun n -> n + 1;; (* applying a function to a value *) (fun n -> n + 1) 2;; (* ⇒ 3 *)
The way -> is defined, a function always takes one argument and returns only one element. A function with multiple parameters can be translated into a sequence of unary functions.
The tail recursive function uses an accumulator, a, to store the value of the result of the previous call. This allows OCaml to perform tail call optimization which results in the the stack not overflowing.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With