Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the difference between these two recursive ocaml functions?

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?

like image 822
SKLAK Avatar asked Mar 04 '14 01:03

SKLAK


People also ask

What are functions in OCaml?

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 *)

What does -> mean in OCaml?

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.

What is tail recursion OCaml?

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.


1 Answers

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.

like image 162
gautamc Avatar answered Nov 15 '22 10:11

gautamc