-1
let rec f1 = fun x -> if x = 0 then 1 else f1 (f1 0) in ...

let rec f2 = fun x -> if x = 0 then foo x else f2 x in ...

where foo isn't tail recursive

let rec f3 = fun x -> if x = 0 then foo x else f3 x in ...

where foo is tail recursive

2
  • What language is that?
    – Bergi
    May 25, 2016 at 17:15
  • none of those are actually recursive at all, since x is passed as-is.
    – njzk2
    May 25, 2016 at 17:18

2 Answers 2

1

You shouldn't be asking whether the function is tail recursive. You should be asking whether all calls are tail calls. Additionally, whether foo is tail recursive or not is actually not relevant—a tail call is a tail call irrespective of which function it calls.

So let's take them one at a time:

let rec f1 = fun x -> if x = 0 then 1 else f1 (f1 0) in ...

In the else, the inner call to f1 is not a tail call. The outer one is. Note that this means that, depending on how you define the term, you could either say that this function is tail recursive (it's got a tail call to itself) or that it isn't (it's got a non-tail call to itself).

This is why it's important to focus on which calls are tail calls, not tail recursion! A language with tail-call elimination will do it for the outer call but not the inner one.

let rec f2 = fun x -> if x = 0 then foo x else f2 x in ...
let rec f3 = fun x -> if x = 0 then foo x else f3 x in ...

The calls to foo and to f2 are tail calls in both cases. Again, it doesn't matter what foo is.

0

All of them are tail recursive.

f1 however does contain two recursive calls, of which only the outer is a tail call.

For f2/f3, it does not matter whether foo is tail-recursive or not, because it is not part of the recursion of f2/f3 at all.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.