Sign up ×


share|improve this question
For curious: both while and whilst have been in the language for a very long time. While was in use in Old English; whilst is a Middle English development of while. As conjunctions they are interchangeable in meaning, but whilst has not survived in standard American English. – Filip Bartuzi Oct 18 '14 at 23:02
Maybe it is late, but this is a pretty good article about tail – Zhisheng Aug 8 at 18:14

16 Answers 16

up vote 752 down vote accepted



Here is a simple Python implementation that uses recursion:

def recsum(x):
 if x == 1:
  return x
  return x + recsum(x - 1)


5 + recsum(4)
5 + (4 + recsum(3))


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

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
    return tailrecsum(x - 1, running_total + x)


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



share|improve this answer
@Paco, what was the link? Was it some kind of a joke? It is 404, do you have a mirror? :-) – tillda Aug 29 '12 at 23:41
@tillda: Yes a joke. Here is a mirror: – Paco Sep 18 '12 at 14:34




share|improve this answer
@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 '13 at 19:16
@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 '14 at 22:58
Scala does but you need the @tailrec specified to enforce it. – SilentDirge Dec 26 '14 at 21:02
"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 at 21:12


while(E) { S }; return Q




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

is equivalent to the tail-recursive function(s)

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

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


share|improve this answer
@Imray The tail-recursive part is the "return sum_aux" statement inside sum_aux. – Chris Conway Mar 11 '13 at 4:51



function f (x)
  return g(x)



function foo (n)



function room1 ()
  local move =
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room

function room2 ()
  local move =
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()

function room3 ()
  local move =
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()

function room4 ()

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


share|improve this answer
The link is broken. It should be – Alexander Gladysh Jun 18 '10 at 2:40
This is a great answer because it explains the implications of tail calls upon stack size. – Andrew Swan Aug 22 '14 at 7:32
@AndrewSwan Indeed, although I believe that the original asker and the occasional reader who might stumble into this question might be better served with the accepted answer (since he might not know what the stack actually is.) By the way I use Jira, big fan. – Hoffmann Aug 22 '14 at 13:47


(define (factorial x)
  (if (= x 0) 1

Here is a version of factorial that is tail-recursive:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
    (lambda (x)
      (fact x 1))))


share|improve this answer



Basically Tail recursions are able to be optimized into iteration.

share|improve this answer


tail recursion /n./

If you aren't sick of it already, see tail recursion.

share|improve this answer



share|improve this answer
Neat article, thanks! – vtortola Nov 12 '14 at 12:45



factorial(x, fac) {
  if (x == 1)
     return fac;
     return factorial(x-1, x*fac);


share|improve this answer


public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);

    if (iter == n)
        return acc;

Contrast this with the standard recursive implementation:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
share|improve this answer


Very simple and intuitive to understand.



public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
share|improve this answer
0! is 1. So "mynumber == 1" should be "mynumber == 0". – polerto Mar 5 '14 at 23:35


(defun ! (n &optional (product 1))
    (if (zerop n) product


share|improve this answer



share|improve this answer


sub tail_rec_sum($;$){

  return $running_total unless $x;

  goto &tail_rec_sum; # throw away current stack frame
share|improve this answer

To understand some of the core differences between tail-call recursion and non-tail-call recursion we can explore the .NET implementations of these techniques.

Here is an article with some examples in C#, F#, and C++\CLI: Adventures in Tail Recursion in C#, F#, and C++\CLI.

C# does not optimize for tail-call recursion whereas F# does.

The differences of principle involve loops vs. Lambda calculus. C# is designed with loops in mind whereas F# is built from the principles of Lambda calculus. For a very good (and free) book on the principles of Lambda calculus, see: Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman.

Regarding tail calls in F#, for a very good introductory article , see: Detailed Introduction to Tail Calls in F#. Finally, here is an article that covers the difference between non-tail recursion and tail-call recursion (in F#): Tail-recursion vs. non-tail recursion in F sharp.

If you want to read about some of the design differences of tail-call recursion between C# and F#, see: Generating Tail-Call Opcode in C# and F#.

If you care enough to want to know what conditions prevent the C# compiler from performing tail-call optimizations, see this article: JIT CLR tail-call conditions.

share|improve this answer

Recursion means a function calling itself. For example:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Tail-Recursion means the recursion that conclude the function:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))


(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        (helper (cons (op (car left))
                (cdr left))))
  (reverse (helper '() lst)))



share|improve this answer

protected by Srikar Appal Aug 4 '13 at 15:27


Would you like to answer one of these unanswered questions instead?
