Short question is: what can qualify for potential tail call recursion optimization (TCO) or tail recursion elimination (TRE) if the compiler or interpreter supports it.The summary of this question is in the section Or is it true that, one simplest way to think about it below.I saw the Stack Overflow question What is tail-recursion elimination? as well, and read different descriptions of how a tail call recursion can happen.First one:a tail call is a subroutine call performed as the final action of a procedure (Wikipedia as of Jan 10, 2016)Second one:when the value returned by the recursive call is itself immediately returned (Programming Interview Exposed, Wiley, 2013)Third one:when a function calls itself, it cannot do any operation with this value that involves a local variable, and just return it. This call happens at the end of function, and so any local variables or state inside the stack (inside the current scope) can be thrown awayI think the second one is very close to the third one, except I didn't see exactly what it mean by immediately.  The first one made me think if I return n * fact(n-1) then it qualifies, although later on in Wikipedia, it says n * fact(n - 1) is not tail recursive, because even though it calls itself on the last line, it uses n, so it doesn't qualify for TCO.Interestingly, maybe the book Programming Interview Exposed 2013, Wiley, needs an errata, that it saysint factorial( int n ) {    if (n > 1) {         /* Recursive case */        return factorial(n-1) * n;     } else {         /* Base case */        return 1;     }}when the value returned by the recursive call is itself immediately returned, as in the preceding definition for factorial, the function is tail-recursive. Some compilers can perform tail call elimination on tail-recursive functions, an optimization that reuses the same stack frame for each recursive callbut I don't think it is tail recursive, is it?Is calling on the last line important? On the page Tail Call Optimization in Ruby it says the following code can qualify for TCO:def fact(n, acc=1)             # just assuming we pass in non-negative n  return acc if n <= 1  return fact(n-1, n*acc)endBut isn't it true that even the following qualify for TCO?def fact(n, acc=1)  return fact(n-1, n*acc) if n > 1  return acc if n <= 1endOr is it not, because it has unfinished business -- you need the stack to remember where the code has reached and continue later on, so you cannot wipe out the stack?What if you do math operation, but it is like return 1 + fact(n-1)?  That is, you are adding a constant, 1 instead of touching any local variable, so there shouldn't be stack info that needs to be kept each time you recurs.  But if you view it as needing to remember 1 + (1 + (1 + (1 + ..., then in fact you still need more and more stack, unless if typical TCO can actually optimize it to 4 + fact(...) without needing new stacks.Or is it true that, one simplest way to think about it is:When you can wipe out the whole stack frame, because there is no need to keep any of those info in the current stack when you make the recursive call, then you can wipe the whole stack frame out and just use a GO TO, instead of adding a new stack, then it can qualify for TCO?  Then, at least for this recursive call alone, there will be no stack overflow.So because if you can wipe out the whole stack frame, that means, there is no local variables that is needed?What if it is a recursive call to traverse a binary tree or rename all files under a directory and all its subdirectories, from the form Programming_Ruby.pdf to Programming Ruby.pdf, and your recursion is not on the last line, because the last line has a print this folder done... then, can you wipe the whole stack frame out?  That is, will the position of the next line of code to run also depend on the stack frame?If the next line to run depends on the stack, then maybe it can boil down to these 2 rules?the recursive call must be the last operation of the function, so after this recursive call, the current function will end and there is no next line of code to run to remember.there must be no operation involved with this recursive call.  No math operations, whatsoever, especially if it involves a local variable.  It must simply return f(...) and return it alone. (or call this procedure alone). The ... inside can involve calculations, even if it involves local variables.  Outside of (...) you cannot do any calculation at all.
What can qualify for potential tail call recursion (TCO) optimization or tail recursion elimination (TRE)
optimization;recursion;tail call