How can I use the let in construct to guarantee a function is either forward or tail recursive?

Learning
1

I was told I could use the let f x1 x2 let a=exp1 in b = exp2 to force a function to be forward or tail recursive (without needing to memorize the semantics or order of evaluation of things in Ocaml). I was trying to see examples of this. Can anyone show me an example of this?

Let me share my general thoughts for the moment.

I know that forward recursion is when we compute the recursive call first. e.g. when the function evals start getting expanded until at the very end once we get to the base case we can do the actual computation. So what I think would be an example is to put the recursive call in for expresion exp1.
So I think the following is forward recursive but it doesn’t use the let in construct:

let rec sum_forward n =
match n with
| 1 -> 1
| _ -> n + sum_forward (n-1);;

This is forward cuz the n + cannot be done until the recursion has been totally unfolded until the base case. According to me this is how to make it forward recursive:

let rec sum_forward' n = let recursion = sum_forward (n-1) in
match n with
| 1 -> 1
| _ -> n + recursion;;

For sure using the let in operation. Is this correct? Is there something weird or some edge case I should consider that I might be missing? I just don’t know for sure if this is right.

Now I am trying to think if it ever makes sense to use the let in to force something to be tail recursive. Is this possible or make sense?

2

Using let ... in ... doesn’t have anything to do with a function being tail-recursive or not. Tail recursion happens when every branch of the function is either not recursive, or only a recursive call to itself, with no further evaluation steps after the recursive call.

OCaml has a @tailcall annotation that can be used to enforce at compile time that a function is tail-recursive–which is really helpful when you need it. See https://stackoverflow.com/q/38843684/20371

1 Like