What is tail recursion?

One of the great benefits of identifying a tail-recursive function is that it can be converted into an iterative form and thus reliving the algorithm from method-stack-overhead. Might like to visit response from @Kyle Cronin and few others below

@majurageerthan - that's depends on the particular implementation of those (and any other) algorithms.

30 Answers 30

Consider a simple function that adds the first N natural numbers. (e.g. sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15 ).

Here is a simple JavaScript implementation that uses recursion:

function recsum(x) < if (x === 0) < return 0; >else < return x + recsum(x - 1); >> 

If you called recsum(5) , this is what the JavaScript interpreter would evaluate:

recsum(5) 5 + recsum(4) 5 + (4 + recsum(3)) 5 + (4 + (3 + recsum(2))) 5 + (4 + (3 + (2 + recsum(1)))) 5 + (4 + (3 + (2 + (1 + recsum(0))))) 5 + (4 + (3 + (2 + (1 + 0)))) 5 + (4 + (3 + (2 + 1))) 5 + (4 + (3 + 3)) 5 + (4 + 6) 5 + 10 15 

Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.

Here's a tail-recursive version of the same function:

function tailrecsum(x, running_total = 0) < if (x === 0) < return running_total; >else < return tailrecsum(x - 1, running_total + x); >> 

Here's the sequence of events that would occur if you called tailrecsum(5) , (which would effectively be tailrecsum(5, 0) , because of the default second argument).

tailrecsum(5, 0) tailrecsum(4, 5) tailrecsum(3, 9) tailrecsum(2, 12) tailrecsum(1, 14) tailrecsum(0, 15) 15 

In the tail-recursive case, with each evaluation of the recursive call, the running_total is updated.

Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don't support tail call optimization. However, while tail call optimization is part of the ECMAScript 2015 spec, most JavaScript interpreters don't support it).

Can I say that with tail recursion the final answer is calculated by the LAST invocation of the method alone? If it is NOT tail recursion you need all the results for all method to calculate the answer.

Here's an addendum that presents a few examples in Lua: lua.org/pil/6.3.html May be useful to go through that as well! :)

Can someone please address chrisapotek's question? I'm confused how tail recursion can be achieved in a language that doesn't optimize away tail calls.

@KevinMeredith "tail recursion" means that the last statement in a function, is a recursive call to the same function. You are correct that there is no point in doing this in a language that doesn't optimize away that recursion. Nevertheless, this answer does show the concept (almost) correctly. It would have been more clearly a tail call, if the "else:" were omitted. Wouldn't change the behavior, but would place the tail call as an independent statement. I will submit that as an edit.

Re the note at the end of the answer: Only JavaScriptCore (from Apple) implements TCO, V8 (in Chrome, Chromium, Node.js, . ), SpiderMonkey (Firefox, etc.), and Chakra (Edge, for now) do not and don't plan to, even though it's in the specification. So on the desktop, only Safari has TCO. (On iOS, Chrome and Firefox and other browsers do because they're forced to use JavaScriptCore instead of their own engines, because non-Apple apps can't allocate executable memory. V8's adding an interpreter-only mode which they may switch to, but. )

In traditional recursion, the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call.

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of (return (recursive-function params)) . Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

The consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.

@Daniel "Basically, the return value of any given recursive step is the same as the return value of the next recursive call."- I fail to see this argument holding true for the code snippet posted by Lorin Hochstein. Can you please elaborate?

@Geek This is a really late response, but that is actually true in Lorin Hochstein's example. The calculation for each step is done before the recursive call, rather than after it. As a result, each stop just returns the value directly from the previous step. The last recursive call finishes the computation and then returns the final result unmodified all the way back down the call stack.

"In this manner, you don't get the result of your calculation until you have returned from every recursive call." -- maybe I misunderstood this, but this isn't particularly true for lazy languages where the traditional recursion is the only way to actually get a result without calling all recursions (e.g. folding over an infinite list of Bools with &&).

An important point is that tail recursion is essentially equivalent to looping. It's not just a matter of compiler optimization, but a fundamental fact about expressiveness. This goes both ways: you can take any loop of the form

while(E) < S >; return Q 

where E and Q are expressions and S is a sequence of statements, and turn it into a tail recursive function

f() = if E then < S; return f() >else

Of course, E , S , and Q have to be defined to compute some interesting value over some variables. For example, the looping function

sum(n) < int i = 1, k = 0; while( i return k; > 

is equivalent to the tail-recursive function(s)

sum_aux(n,i,k) < if( i else < return k; >> sum(n)

(This "wrapping" of the tail-recursive function with a function with fewer parameters is a common functional idiom.)

In the answer by @LorinHochstein I understood, based on his explanation, that tail recursion to be when the recursive portion follows "Return", however in yours, the tail recursive is not. Are you sure your example is properly considered tail recursion?

@lmray: Chris's code is essentially equivalent. The order of the if/then and style of the limiting test. if x == 0 versus if(i<=n). is not something to get hung up on. The point is that each iteration passes its result to the next.

@cOder, you're right but people come to stackoverflow to also learn then maybe use of if and else make it more comprehensive for more beginners, I think

This excerpt from the book Programming in Lua shows how to make a proper tail recursion (in Lua, but should apply to Lisp too) and why it's better.

A tail call [tail recursion] is a kind of goto dressed as a call. A tail call happens when a function calls another as its last action, so it has nothing else to do. For instance, in the following code, the call to g is a tail call:

function f (x) return g(x) end 

After f calls g , it has nothing else to do. In such situations, the program does not need to return to the calling function when the called function ends. Therefore, after the tail call, the program does not need to keep any information about the calling function in the stack. .

Because a proper tail call uses no stack space, there is no limit on the number of "nested" tail calls that a program can make. For instance, we can call the following function with any number as argument; it will never overflow the stack:

function foo (n) if n > 0 then return foo(n - 1) end end 

. As I said earlier, a tail call is a kind of goto. As such, a quite useful application of proper tail calls in Lua is for programming state machines. Such applications can represent each state by a function; to change state is to go to (or to call) a specific function. As an example, let us consider a simple maze game. The maze has several rooms, each with up to four doors: north, south, east, and west. At each step, the user enters a movement direction. If there is a door in that direction, the user goes to the corresponding room; otherwise, the program prints a warning. The goal is to go from an initial room to a final room.

This game is a typical state machine, where the current room is the state. We can implement such maze with one function for each room. We use tail calls to move from one room to another. A small maze with four rooms could look like this:

function room1 () local move = io.read() if move == "south" then return room3() elseif move == "east" then return room2() else print("invalid move") return room1() -- stay in the same room end end function room2 () local move = io.read() if move == "south" then return room4() elseif move == "west" then return room1() else print("invalid move") return room2() end end function room3 () local move = io.read() if move == "north" then return room1() elseif move == "east" then return room4() else print("invalid move") return room3() end end function room4 () print("congratulations!") end 

So you see, when you make a recursive call like:

function x(n) if n==0 then return 0 n= n-2 return x(n) + 1 end 

This is not tail recursive because you still have things to do (add 1) in that function after the recursive call is made. If you input a very high number it will probably cause a stack overflow.