Tail recursion in OCaml, constant stack space

Learning
1 
type t = A of bool * t | B;;
let rec h c = match c with A (v,u) -> v::h u | B -> [];;
`​``
Implement a tail-recursive version of h such that h operates in constant stack
space. Do not change its type!
Here is my solution:
```ocaml
let rec trec c acc = match c with A(u,v) -> trec v (u::acc) | B -> acc;;
let tailrecursiveversion c = List.rev (trec c []);;
`​``
Is this correct answer? why? why not? (just for understanding difference between tail recursion and normal recursion (not homework))
2 Likes
2

There is a rather straightforward way to check this.
First, you construct a very big value (of your type t) such that non tail recursive function crashes with Stackoverflow.
After that you run your tail recursive candidate and observe that it no longer crashes and gives decent answer.

I think giving the answer for question “is the solution correct” not very good for pedagogical reasons :slight_smile:

Happy studying, young camel rider!

P.S. Please, read something about markdown markup…

2 Likes
3

OCaml has a built-in compiler check that a function is tail-recursive, using the [@tailcall] attribute. When used, it will give a compiler warning (51) when the function is not tail-recursive. Here’s an example of a tail-recursive function:

let rec find pred = function
  | [] -> None
  | x :: xs -> if pred x then Some x else (find[@tailcall]) pred xs

And here’s an example that’s not tail-recursive:

let rec map f = function
  | [] -> []
  | x :: xs -> f x :: (map[@tailcall]) f xs

The second example will give a compiler warning. As shown above, the way this attribute works is by ‘attaching’ itself to the recursive call. If it’s not a tail call, then the warning triggers. You can do the same thing with your function.

12 Likes
4

Oh wow, my comment is not productive at all in the discussion, but thank you for that @yawaramin, I didn’t know you could check for that !

1 Like