Categories
algorithm functional-programming language-agnostic recursion tail-recursion

What is tail recursion?

1952

Whilst starting to learn lisp, I’ve come across the term tail-recursive. What does it mean exactly?

7

  • 19

    Maybe it is late, but this is a pretty good article about tail recursive:programmerinterview.com/index.php/recursion/tail-recursion

    – Sam003

    Aug 8, 2015 at 18:14

  • 6

    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

    – KGhatak

    May 25, 2017 at 16:57


  • This link from @yesudeep is the best, most detailed description I’ve found – lua.org/pil/6.3.html

    Jan 2, 2019 at 16:43

  • 1

    Could someone tell me, Do merge sort and quick sort use tail recursion (TRO) ?

    Jan 23, 2020 at 16:02


  • 2

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

    Nov 9, 2020 at 23:01

1987

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.

10

  • 68

    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.

    Dec 8, 2012 at 20:34


  • 3

    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! 🙂

    – yesudeep

    Feb 28, 2013 at 7:24


  • 3

    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.

    May 15, 2013 at 19:29

  • 7

    @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.

    Dec 12, 2013 at 21:33

  • 4

    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…)

    May 22, 2019 at 18:20

800

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.

9

  • 22

    “I’m pretty sure Lisp does this” — Scheme does, but Common Lisp doesn’t always.

    – Aaron

    Jan 2, 2009 at 23:51

  • 2

    @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

    Mar 20, 2013 at 19:16

  • 9

    @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.

    – reirab

    Apr 23, 2014 at 22:58

  • 4

    Scala does but you need the @tailrec specified to enforce it.

    Dec 26, 2014 at 21:02

  • 2

    “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 &&).

    – hasufell

    Jun 30, 2015 at 21:12

227

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 { return Q }

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 <= n ) {
    k += i;
    ++i;
  }
  return k;
}

is equivalent to the tail-recursive function(s)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

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

6

  • 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?

    Mar 10, 2013 at 22:44

  • 1

    @Imray The tail-recursive part is the “return sum_aux” statement inside sum_aux.

    Mar 11, 2013 at 4:51

  • 2

    @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.

    – Taylor

    Sep 27, 2013 at 18:24

  • else { return k; } can be changed to return k;

    – c0der

    Jun 13, 2018 at 5:41


  • @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

    Mar 13, 2021 at 2:17