CODEWITHSUNDEEP
ocamltail-recursion
Juliana Souza
Juliana Souza

Reputation: 69

OCaml: How Can I execute a program that uses Tail Recursion?

I'm writing a function using Tail Recursion, but I don't know to execute. Normally, I use ocaml QuicksortTail.ml Qsort, but the error is displayed when I execute for a list with 70000 elements:

Fatal error: exception Stack_overflow"

let rec trev l r = 
    match l with
        | [] -> r
        | x::xs -> trev xs (x::r);;
let rev l = trev l [];;

List.iter (fun x->print_int x) (rev[5;4;3;2;1])

My oCaml is 4.01.

Upvotes: 2

Views: 185

Answers (2)

ivg
ivg

Reputation: 35210

The tail recursion is a particular kind of recursion where a recursive call is the last call in a function. It is not a mode of execution, so you don't need to pass any specific flags to an interpreter or to a compiler to enable or disable tail recursion. It is a static property of your program.

When a call is in a tail position, (it doesn't really matter whether it is a recursive call or not), the OCaml compiler will emit a code, that doesn't use the stack space. The same is true for the interpreter. A call will not consume the stack space, thus you can perform a virtually infinite number of tail calls without getting a stack overflow.

Since you're getting the stack overflow, it means that something is not tail-recursive. The code that you just showed is fine, and perfectly tail recursive, thus it is some other code, that actually throws an exception. Not your rev.

Upvotes: 3

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66803

@RichouHunter is correct as far as I can see.

Just for completeness, here is a toplevel session showing that your code works fine:

$ rlwrap ocaml
        OCaml version 4.03.0

# let rec trev l r =
    match l with
        | [] -> r
        | x::xs -> trev xs (x::r);;
val trev : 'a list -> 'a list -> 'a list = <fun>
# let rev l = trev l [];;
val rev : 'a list -> 'a list = <fun>

# let rec range accum m n = if m > n then accum else range (n :: accum) m (n - 1);;
val range : int list -> int -> int -> int list = <fun>

# let big = range [] 1 70000;;
val big : int list =
  [1; 2; 3; ...]
# let revbig = rev big;;
val revbig : int list =
  [70000; 69999; 69998; ...]

As @RichouHunter says, there's nothing special to do to run tail recursive code.

Upvotes: 3

Related Questions