CODEWITHSUNDEEP
algorithmrecursiontail-recursion
gekrone
gekrone

Reputation: 179

Nested recursive calls - is this tail recursion?

I think that I understand the textbook definition of a tail recursrive function: a function that doesn't perform any calculations after the function call. I also get that as a consequence a tail recursive function will be more memory efficient, because it will need only one record for every call, instead of needing to keep a record each (as in normal recursion).

What is less clear to me is how does this definition apply to nested calls. I'll provide an example:

func foo91(x int)
    if(x > 100):
        return x - 10
    else:
        return foo91(foo91(x+11))

The answer I originally came up with was that it was not tail recursive by definition (because the external call is performed after evaluating the interal one, so other calculations are done after the first call), so generally functions with nested recursive calls are not tail recursive; on the other hand it is the same in practice, as it shares the side effects of a tail recursive function: it seems to me that a single activation record is needed for the whole function. Is that true?

Are nested recursive function calls generally considerable tail recursive?

Upvotes: 0

Views: 628

Answers (1)

btilly
btilly

Reputation: 46408

Your understanding is only partially correct.

You defined tail recursion correctly. But whether it is actually efficient is implementation dependent. In some languages like Scheme it is. But most languages are like JavaScript and it is not. In particular one of the key tradeoffs is that making tail recursion efficient means you lose stack backtraces.

Now to your actual question, the inner call is not tail recursive because it has to come back to your call and do something else. But the outer call is tail recursive.

Upvotes: 3

Related Questions