algorithm Talk:Tail recursion

algorithm Talk:Tail recursion

Stack Overflow



  1. Log In
    Sign Up

  2. current community


    • Stack Overflow

      help
      chat

    • Meta Stack Overflow

    your communities

    Sign up or log in to customize your list.

    more stack exchange communities

    company blog

    • Tour

      Start here for a quick overview of the site

    • Help Center

      Detailed answers to any questions you might have

    • Meta

      Discuss the workings and policies of this site

    • About Us

      Learn more about Stack Overflow the company

    • Business

      Learn more about hiring developers or posting ads with us

By using our site, you acknowledge that you have read and understand our Cookie Policy , Privacy Policy , and our Terms of Service .

What is tail recursion?

Ask Question


up vote
1384
down vote

favorite

667

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

algorithm language-agnostic functional-programming recursion tail-recursion

share | improve this question

edited Oct 11 ’16 at 2:32


community wiki

10 revs, 7 users 50%
Ben Lever

  • 113

    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

  • 6

    Maybe it is late, but this is a pretty good article about tail recursive: programmerinterview.com/index.php/recursion/tail-recursion
    –  Sam003
    Aug 8 ’15 at 18:14

  • 47

    First, you need to understand recursion. A good comment explaining it is here: stackoverflow.com/questions/33923/…
    –  joe_young
    Jan 16 ’16 at 21:08


  • 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 ’17 at 16:57


  • @joe_young – The tale of magical of recursion. I couldn’t upvote your comment enough. Good one!
    –  RBT
    Mar 2 at 9:35

 | 
show 1 more comment

23 Answers
23

active

oldest

votes


up vote
1376
down vote

accepted

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

Here is a simple JavaScript implementation that uses recursion:

function recsum(x) if (x===1) return x; 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)))
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 modern JavaScript interpreters support tail call optimization but Python interpreters don’t.

share | improve this answer

edited Feb 15 at 16:03

Matthias Braun

13k875108

answered Aug 31 ’08 at 18:21

Lorin Hochstein

33.6k2285123

  • 109

    Python is kind of an odd choice here, since it does not have AFAIK tail-recursion elimination.
    –  Chris Conway
    Sep 21 ’08 at 14:43

  • 10

    Chris Conway is correct. Tail calls are not optimized in Python, unfortunately. Guido claims having the stack available for debugging is better than TCO.
    –  McPherrinM
    Dec 5 ’09 at 3:25

  • 36

    You’ll find Guido’s opinion here .
    –  new123456
    May 14 ’11 at 14:27

  • 2

    @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

  • 109

    @tillda: Yes a joke. Here is a mirror: cs.cmu.edu/~wklieber/python-tail-recursion.jpg
    –  Paco
    Sep 18 ’12 at 14:34

 | 
show 9 more comments


up vote
580
down vote

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.

share | improve this answer

edited Jul 30 at 3:41

henrebotha

694926

answered Aug 29 ’08 at 3:57
user316

  • 10

    "I’m pretty sure Lisp does this" — Scheme does, but Common Lisp doesn’t always.
    –  Aaron
    Jan 2 ’09 at 23:51

  • 1

    @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

  • 7

    @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

  • 1

    "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 ’15 at 21:12

 | 
show 1 more comment


up vote
173
down vote

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

share | improve this answer

edited Aug 12 ’14 at 23:28

Mr. Polywhirl

16.2k84783

answered Aug 31 ’08 at 17:29

Chris Conway

39.1k35114144

  • 9

    Great explanation, but why is your function called fibo? That’s not Fibonacci; it’s f(n) = Binomial(n+1,2)
    –  RexE
    Dec 25 ’11 at 7:29


  • 14

    @RexE Total brain fart. I got upvoted 20 times and nobody pointed that out!
    –  Chris Conway
    Dec 26 ’11 at 14:24

  • 1

    🙂 also make sure to rename the recursive calls.
    –  RexE
    Dec 28 ’11 at 20:45

  • 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?
    –  CodyBugstein
    Mar 10 ’13 at 22:44

  • 1

    @Imray The tail-recursive part is the "return sum_aux" statement inside sum_aux.
    –  Chris Conway
    Mar 11 ’13 at 4:51

 | 
show 2 more comments


up vote
119
down vote

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.

share | improve this answer

edited Feb 25 ’16 at 21:26

Air

4,98723667

answered Aug 29 ’08 at 16:03

Hoffmann

7,276115772

  • 6

    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

  • My favourite answer as well due to including the implication for the stack size.
    –  njk2015
    Jul 17 ’17 at 13:26

add a comment  | 


up vote
60
down vote

Using regular recursion, each recursive call pushes another entry onto the call stack. When the recursion is completed, the app then has to pop each entry off all the way back down.

With tail recursion, depending on language the compiler may be able to collapse the stack down to one entry, so you save stack space…A large recursive query can actually cause a stack overflow.

Basically Tail recursions are able to be optimized into iteration.

share | improve this answer

edited Oct 25 at 13:13

DavidB

1,34621851

answered Aug 29 ’08 at 3:55

FlySwat

112k63231300

add a comment  | 


up vote
59
down vote

Instead of explaining it with words, here’s an example. This is a Scheme version of the factorial function:

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

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

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

You will notice in the first version that the recursive call to fact is fed into the multiplication expression, and therefore the state has to be saved on the stack when making the recursive call. In the tail-recursive version there is no other S-expression waiting for the value of the recursive call, and since there is no further work to do, the state doesn’t have to be saved on the stack. As a rule, Scheme tail-recursive functions use constant stack space.

share | improve this answer

edited Apr 22 ’13 at 22:32

Cristian Ciupitu

14.2k54262

answered Aug 29 ’08 at 3:57

Kyle Cronin

58.2k38136156

  • 3

    +1 for mentioning the most important aspect of tail-recursions that they can be converted into an iterative form and thereby turning it into an O(1) memory complexity form.
    –  KGhatak
    May 25 ’17 at 16:54

  • @KGhatak not exactly; the answer correctly speaks about "constant stack space", not memory in general. not to be nitpicking, just to make sure there’s no misunderstanding. e.g. tail-recursive list-tail-mutating list-reverse procedure will run in constant stack space but will create and grow a data structure on the heap. A tree traversal could use a simulated stack, in an additional argument. etc.
    –  Will Ness
    Oct 6 ’17 at 23:32

add a comment  | 


up vote
56
down vote

The jargon file has this to say about the definition of tail recursion:

tail recursion /n./

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

share | improve this answer

edited Feb 16 ’10 at 17:34

answered Aug 29 ’08 at 7:21

Pat

28.2k186486

  • I see what you did there. Cheeky example there. 😀
    –  Sajib Acharya
    Apr 19 ’16 at 13:50

  • 2

    The comedic value-add and upvotes on this post compensate for the fact that this isn’t an answer.
    –  Eric Leschinski
    Apr 5 ’17 at 3:42

  • 1

    I, seriously, didn’t see this coming.
    –  Mehraj Malik
    May 11 ’17 at 7:03


add a comment  | 


up vote
26
down vote

Tail recursion refers to the recursive call being last in the last logic instruction in the recursive algorithm.

Typically in recursion you have a base-case which is what stops the recursive calls and begins popping the call stack. To use a classic example, though more C-ish than Lisp, the factorial function illustrates tail recursion. The recursive call occurs after checking the base-case condition.

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

Note, the initial call to factorial must be factorial(n, 1) where n is the number for which the factorial is to be calculated.

share | improve this answer

edited Aug 12 ’14 at 23:30

Mr. Polywhirl

16.2k84783

answered Aug 29 ’08 at 3:57

Peter Meyer

20.9k12851

  • I found your explanation easiest to understand, but if it’s anything to go by, then tail recursion is only useful for functions with one statement base cases. Consider a method such as this postimg.cc/5Yg3Cdjn . Note: the outer else is the step you might call a "base case" but spans across several lines. Am I misunderstanding you or is my assumption correct? Tail recursion is only good for one liners?
    –  I Want Answers
    Oct 23 at 19:27


add a comment  | 


up vote
24
down vote

It means that rather than needing to push the instruction pointer on the stack, you can simply jump to the top of a recursive function and continue execution. This allows for functions to recurse indefinitely without overflowing the stack.

I wrote a blog post on the subject, which has graphical examples of what the stack frames look like.

share | improve this answer

answered Aug 31 ’08 at 23:52

Chris Smith

11k94874

add a comment  | 


up vote
15
down vote

Here is a quick code snippet comparing two functions. The first is traditional recursion for finding the factorial of a given number. The second uses tail recursion.

Very simple and intuitive to understand.

An easy way to tell if a recursive function is a tail recursive is if it returns a concrete value in the base case. Meaning that it doesn’t return 1 or true or anything like that. It will more than likely return some variant of one of the method parameters.

Another way is to tell is if the recursive call is free of any addition, arithmetic, modification, etc… Meaning its nothing but a pure recursive call.

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

edited Nov 23 at 14:25


community wiki

3 revs, 3 users 86%
AbuZubair

  • 3

    0! is 1. So "mynumber == 1" should be "mynumber == 0".
    –  polerto
    Mar 5 ’14 at 23:35

add a comment  | 


up vote
11
down vote

The best way for me to understand tail call recursion is a special case of recursion where the last call(or the tail call) is the function itself.

Comparing the examples provided in Python:

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

^RECURSION

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

^TAIL RECURSION

As you can see in the general recursive version, the final call in the code block is x + recsum(x - 1). So after calling the recsum method, there is another operation which is x + ...

However, in the tail recursive version, the final call(or the tail call) in the code block is tailrecsum(x - 1, running_total + x) which means the last call is made to the method itself and no operation after that.

This point is important because tail recursion as seen here is not making the memory grow because when the underlying VM sees a function calling itself in a tail position (the last expression to be evaluated in a function), it eliminates the current stack frame, which is known as Tail Call Optimization(TCO).

EDIT

NB. Do bear in mind that the example above is written in Python whose runtime does not support TCO. This is just an example to explain the point. TCO is supported in languages like Scheme, Haskell etc

share | improve this answer

edited Nov 23 at 14:27


community wiki

4 revs, 2 users 94%
Abhiroop Sarkar

  • 1

    This answers helped me to understand "tail recursion" definition finally
    –  2442396
    Mar 2 at 22:15

add a comment  | 


up vote
10
down vote

In Java, here’s a possible tail recursive implementation of the Fibonacci function:

public int tailRecursive(final int n) if (n <= 2) return 1; return tailRecursiveAux(n, 1, 1);
private int tailRecursiveAux(int n, int iter, int acc) if (iter == n) return acc; return tailRecursiveAux(n, ++iter, acc + iter);

Contrast this with the standard recursive implementation:

public int recursive(final int n) if (n <= 2) return 1; return recursive(n - 1) + recursive(n - 2);

share | improve this answer

edited Aug 12 ’14 at 23:24

Mr. Polywhirl

16.2k84783

answered Oct 14 ’08 at 21:20

jorgetown

390112

  • 1

    This is returning wrong results for me, for input 8 I get 36, it has to be 21. Am I missing something? I’m using java and copy pasted it.
    –  Alberto Zaccagni
    Nov 28 ’11 at 21:21

  • 1

    This returns SUM(i) for i in [1, n]. Nothing to do with Fibbonacci. For a Fibbo, you need a tests which substracts iter to acc when iter < (n-1).
    –  Askolein
    Mar 15 ’13 at 13:44

add a comment  | 


up vote
8
down vote

Here is a Common Lisp example that does factorials using tail-recursion. Due to the stack-less nature, one could perform insanely large factorial computations …

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

And then for fun you could try (format nil "~R" (! 25))

share | improve this answer

edited Aug 12 ’14 at 23:27


community wiki

3 revs, 2 users 71%
user922475

add a comment  | 


up vote
8
down vote

In short, a tail recursion has the recursive call as the last statement in the function so that it doesn’t have to wait for the recursive call.

So this is a tail recursion i.e. N(x – 1, p * x) is the last statement in the function where the compiler is clever to figure out that it can be optimised to a for-loop (factorial). The second parameter p carries the intermediate product value.

function N(x, p) return x == 1 ? p : N(x - 1, p * x);

This is the non-tail-recursive way of writing the above factorial function (although some C++ compilers may be able to optimise it anyway).

function N(x) return x == 1 ? 1 : x * N(x - 1);

but this is not:

function F(x) if (x == 1) return 0; if (x == 2) return 1; return F(x - 1) + F(x - 2);

I did write a long post titled ” Understanding Tail Recursion – Visual Studio C++ – Assembly View “

enter image description here

share | improve this answer

edited Feb 8 ’17 at 23:23


community wiki

4 revs, 2 users 97%
SteakOverCooked

  • 1

    How is your function N tail-recursive ?
    –  Fabian Pijcke
    Dec 30 ’16 at 8:30

  • N(x-1) is the last statement in the function where the compiler is clever to figure out that it can be optimised to a for-loop (factorial)
    –  Zhihua Lai
    Dec 31 ’16 at 10:28

  • My concern is that your function N is exactly the function recsum from the accepted answer of this topic (except that it is a sum and not a product), and that recsum is said to be non tail-recursive ?
    –  Fabian Pijcke
    Dec 31 ’16 at 12:04

  • you are right, my mistake, re-edit the answer.
    –  Zhihua Lai
    Dec 31 ’16 at 14:23

add a comment  | 


up vote
7
down vote

here is a Perl 5 version of the tailrecsum function mentioned earlier.

sub tail_rec_sum($;$) my( $x,$running_total ) = (@_,0); return $running_total unless $x; @_ = ($x-1,$running_total+$x); goto &tail_rec_sum; # throw away current stack frame

share | improve this answer

edited Aug 12 ’14 at 23:29

Mr. Polywhirl

16.2k84783

answered Oct 1 ’08 at 22:06

Brad Gilbert

23.5k862106

add a comment  | 


up vote
6
down vote

I’m not a Lisp programmer, but I think this will help.

Basically it’s a style of programming such that the recursive call is the last thing you do.

share | improve this answer

answered Aug 29 ’08 at 3:50

Matt Hamilton

162k54355305

add a comment  | 


up vote
4
down vote

This is an excerpt from Structure and Interpretation of Computer Programs about tail recursion.

In contrasting iteration and recursion, we must be careful not to
confuse the notion of a recursive process with the notion of a
recursive procedure. When we describe a procedure as recursive, we are
referring to the syntactic fact that the procedure definition refers
(either directly or indirectly) to the procedure itself. But when we
describe a process as following a pattern that is, say, linearly
recursive, we are speaking about how the process evolves, not about
the syntax of how a procedure is written. It may seem disturbing that
we refer to a recursive procedure such as fact-iter as generating an
iterative process. However, the process really is iterative: Its state
is captured completely by its three state variables, and an
interpreter need keep track of only three variables in order to
execute the process.

One reason that the distinction between process and procedure may be
confusing is that most implementations of common languages (including Ada, Pascal, and
C) are designed in such a way that the interpretation of any recursive
procedure consumes an amount of memory that grows with the number of
procedure calls, even when the process described is, in principle,
iterative. As a consequence, these languages can describe iterative
processes only by resorting to special-purpose “looping constructs”
such as do, repeat, until, for, and while. The implementation of
Scheme does not share this defect. It
will execute an iterative process in constant space, even if the
iterative process is described by a recursive procedure. An
implementation with this property is called tail-recursive.
With a
tail-recursive implementation, iteration can be expressed using the
ordinary procedure call mechanism, so that special iteration
constructs are useful only as syntactic sugar.

share | improve this answer

answered Jun 27 ’16 at 9:41


community wiki

ayushgp

  • 1

    I read through all answers here, and yet this is the most clear explanation which touches the really deep core of this concept. It explains it in such a straight way which makes everything looks so simple and so clear. Forgive my rudeness please. It somehow makes me feel like the other answers just do not hit the nail on the head. I think that is why SICP matters.
    –  englealuze
    Jan 24 at 20:58


add a comment  | 


up vote
4
down vote

Tail recursion is the life you are living right now. You constantly recycle the same stack frame, over and over, because there’s no reason or means to return to a “previous” frame. The past is over and done with so it can be discarded. You get one frame, forever moving into the future, until your process inevitably dies.

The analogy breaks down when you consider some processes might utilize additional frames but are still considered tail-recursive if the stack does not grow infinitely.

share | improve this answer

answered Dec 23 ’16 at 18:04


community wiki

user633183

  • 1

    it doesn’t break under split personality disorder interpretation. 🙂 A Society of Mind; a Mind as a Society. 🙂
    –  Will Ness
    Oct 4 at 14:08


add a comment  | 


up vote
4
down vote

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

edited Nov 23 at 14:28


community wiki

4 revs, 2 users 87%
devinbost

add a comment  | 


up vote
3
down vote

A tail recursion is a recursive function where the function calls
itself at the end (“tail”) of the function in which no computation is
done after the return of recursive call. Many compilers optimize to
change a recursive call to a tail recursive or an iterative call.

Consider the problem of computing factorial of a number.

A straightforward approach would be:

 factorial(n): if n==0 then 1 else n*factorial(n-1)

Suppose you call factorial(4). The recursion tree would be:

 factorial(4) / \ 4 factorial(3) / \ 3 factorial(2) / \ 2 factorial(1) / \
1 factorial(0) \ 1 

The maximum recursion depth in the above case is O(n).

However, consider the following example:

factAux(m,n):
if n==0 then m;
else factAux(m*n,n-1);
factTail(n): return factAux(1,n);

Recursion tree for factTail(4) would be:

factTail(4) |
factAux(1,4) |
factAux(4,3) |
factAux(12,2) |
factAux(24,1) |
factAux(24,0) | 24

Here also, maximum recursion depth is O(n) but none of the calls adds any extra variable to the stack. Hence the compiler can do away with a stack.

share | improve this answer

answered Dec 23 ’17 at 12:26


community wiki

coding_ninza

  • I like diagrams!
    –  Felipe Gutierrez
    Nov 29 at 20:57

add a comment  | 


up vote
3
down vote

There are two basic kinds of recursions: head recursion and tail recursion.

In head recursion, a function makes its recursive call and then
performs some more calculations, maybe using the result of the
recursive call, for example.

In a tail recursive function, all calculations happen first and
the recursive call is the last thing that happens.

Taken from this super awesome post.
Please consider reading it.

share | improve this answer

answered May 8 at 10:09


community wiki

Abdullah Khan

add a comment  | 


up vote
3
down vote

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

See, the last thing un-ended function (procedure, in Scheme jargon) does is to call itself. Another (more useful) example is:

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

In the helper procedure, the LAST thing it does if the left is not nil is to call itself (AFTER cons something and cdr something). This is basically how you map a list.

The tail-recursion has a great advantage that the interpreter (or compiler, dependent on the language and vendor) can optimize it, and transform it into something equivalent to a while loop. As matter of fact, in Scheme tradition, most “for” and “while” loop is done in a tail-recursion manner (there is no for and while, as far as I know).

share | improve this answer

edited Nov 23 at 15:17

Sayed Mohd Ali

532216

answered Sep 2 ’08 at 14:08

magice

17713

add a comment  | 


up vote
2
down vote

This question has a lot of great answers… but I cannot help but chime in with an alternative take on how to define “tail recursion”, or at least “proper tail recursion.” Namely: should one look at it as a property of a particular expression in a program? Or should one look at it as a property of an implementation of a programming language?

For more on the latter view, there is a classic paper by Will Clinger, “Proper Tail Recursion and Space Efficiency” (PLDI 1998), that defined “proper tail recursion” as a property of a programming language implementation. The definition is constructed to allow one to ignore implementation details (such as whether the call stack is actually represented via the runtime stack or via a heap-allocated linked list of frames).

To accomplish this, it uses asymptotic analysis: not of program execution time as one usually sees, but rather of program space usage. This way, the space usage of a heap-allocated linked list vs a runtime call stack ends up being asymptotically equivalent; so one gets to ignore that programming language implementation detail (a detail which certainly matters quite a bit in practice, but can muddy the waters quite a bit when one attempts to determine whether a given implementation is satisfying the requirement to be “property tail recursive”)

The paper is worth careful study for a number of reasons:

  • It gives an inductive definition of the tail expressions and tail calls of a program. (Such a definition, and why such calls are important, seems to be the subject of most of the other answers given here.)

    Here are those definitions, just to provide a flavor of the text:

    Definition 1 The tail expressions of a program written in Core Scheme are defined inductively as follows.

    1. The body of a lambda expression is a tail expression
    2. If (if E0 E1 E2) is a tail expression, then both E1 and E2 are tail expressions.
    3. Nothing else is a tail expression.

    Definition 2 A tail call is a tail expression that is a procedure call.

(a tail recursive call, or as the paper says, “self-tail call” is a special case of a tail call where the procedure is invoked itself.)

  • It provides formal definitions for six different “machines” for evaluating Core Scheme, where each machine has the same observable behavior except for the asymptotic space complexity class that each is in.

    For example, after giving definitions for machines with respectively, 1. stack-based memory management, 2. garbage collection but no tail calls, 3. garbage collection and tail calls, the paper continues onward with even more advanced storage management strategies, such as 4. “evlis tail recursion”, where the environment does not need to be preserved across the evaluation of the last sub-expression argument in a tail call, 5. reducing the environment of a closure to just the free variables of that closure, and 6. so-called “safe-for-space” semantics as defined by Appel and Shao .

  • In order to prove that the machines actually belong to six distinct space complexity classes, the paper, for each pair of machines under comparison, provides concrete examples of programs that will expose asymptotic space blowup on one machine but not the other.


(Reading over my answer now, I’m not sure if I’m managed to actually capture the crucial points of the Clinger paper . But, alas, I cannot devote more time to developing this answer right now.)

share | improve this answer

answered Jul 5 ’17 at 10:51


community wiki

pnkfelix

add a comment  | 

protected by Srikar Appalaraju Aug 4 ’13 at 15:27

Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count ).

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

Not the answer you’re looking for? Browse other questions tagged algorithm language-agnostic functional-programming recursion tail-recursion or ask your own question .

asked

10 years, 3 months ago

viewed

350,022 times

active

11 days ago

Blog

Welcome Wagon: Community and Comments on Stack Overflow


Linked

18

The difference between head & tail recursion

2

What is tail recursion optimization?

-1

Another Coder Confused by Recursion

0

Matlab – Tail recursive vector sum

-1

Recursive Squares

3

What is the difference between recursion and tail-recursion?

0

Can anyone explain step by step process (recursion) for below example :

0

What allows tail recursion to work with one stack?

623

What Is Tail Call Optimization?

247

Is recursion ever faster than looping?

see more linked questions…

Related

1266

What is a monad?

7343

What and where are the stack and heap?

2745

What is dependency injection?

623

What Is Tail Call Optimization?

4628

What is a plain English explanation of “Big O” notation?

757

Getting started with Haskell

1149

What is (functional) reactive programming?

1446

Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition

768

“What part of Hindley-Milner do you not understand?”

1792

What is the optimal algorithm for the game 2048?

Hot Network Questions

  • Let’s say a 1 ton sphere of tungsten moving at 99.99% the speed of light hits earth, what happens? Exactly as possible

  • What does the g stand for in gcount, tellg and seekg?

  • Does Sultai Ascendancy interact with cards that care about surveil?

  • Can a creature with truesight see the invisible sensor created by the Clairvoyance spell?

  • An object that is gold in one specific area but becomes worthless if you leave that area?

  • Cannot be granted promotion due to Company Policy

  • Can I Ready an action to do something I’m not currently capable of doing?

  • What definitions were crucial to further understanding?

  • What are the ethical concerns of giving a notice period to an incompetent employee when it’s not required by contract?

  • What is the function of this complicated tensioning system?

  • What is this glass (???) for?

  • Does allowing death saving throws after being stable break the game?

  • A definition of "Done" in case of many Development Teams working on a single product

  • If it is not going to actively heated or cooled, is there any value in insulating a garage?

  • Using a 12 V 3 A bilge pump on a 12 V 8.5 A LED power supply

  • Does wire color matter in electronics?

  • When do we use the word "entry"?

  • Can anyone identify this control panel for a 4 engine plane

  • should I learn measure theory before learning probability?

  • Is it possible to get the "Dragon rend" shout without killing Alduin?

  • How do I read line by line in a file using while loop, and in each iteration, grep each line to compare to a string?

  • OpenVPN unable to disable encryption

  • Can an undirected graph be disconnected?

  • What does this control do on new airplanes?

more hot questions


question feed

Stack Overflow works best with JavaScript enabled

Tail call

From Wikipedia, the free encyclopedia

Jump to navigation
Jump to search

In computer science , a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of recursion . Tail recursion (or tail-end recursion) is particularly useful, and often easy to handle in implementations.

Tail calls can be implemented without adding a new stack frame to the call stack . Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient structured programming . In the words of Guy L. Steele , “in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions.” [1]

Not all programming languages require tail call elimination. However, in functional programming languages , tail call elimination is often guaranteed by the language standard , allowing tail recursion to use a similar amount of memory as an equivalent loop . The special case of tail recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize sibling calls, or tail calls to functions which take and return the same types as the caller. [2]

Contents

  • 1 Description
  • 2 Syntactic form
  • 3 Example programs
  • 4 Tail recursion modulo cons
    • 4.1 Prolog example
    • 4.2 C example
  • 5 History
  • 6 Implementation methods
    • 6.1 In assembly
    • 6.2 Through trampolining
  • 7 Relation to while construct
  • 8 By language
  • 9 See also
  • 10 Notes
  • 11 References

Description[ edit ]

When a function is called, the computer must “remember” the place it was called from, the return address , so that it can return to that location with the result once the call is complete. Typically, this information is saved on the call stack , a simple list of return locations in order of the times that the call locations they describe were reached. For tail calls, there is no need to remember the caller – instead, tail call elimination leaves the stack alone (except possibly for function arguments and local variables , [3] ) and the newly-called function will return directly to the original caller. The tail call doesn’t have to appear lexically after all other statements in the source code; it is only important that the calling function return immediately after the tail call, returning the tail call’s result if any, since the calling function will never get a chance to do anything after the call if the optimization is performed.

For non-recursive function calls, this is usually an optimization that saves only a little time and space, since there are not that many different functions available to call. When dealing with recursive or mutually recursive functions where recursion happens through tail calls, however, the stack space and the number of returns saved can grow to be very significant, since a function can call itself, directly or indirectly, creating a new call stack frame each time. Tail call elimination often asymptotically reduces stack space requirements from linear, or O (n), to constant, or O (1). Tail call elimination is thus required by the standard definitions of some programming languages, such as Scheme , [4] [5] and languages in the ML family among others. The Scheme language definition formalizes the intuitive notion of tail position exactly, by specifying which syntactic forms allow having results in tail context. [6] Implementations allowing an unlimited number of tail calls to be active at the same moment, thanks to tail call elimination, can also be called ‘properly tail-recursive’. [4]

Besides space and execution efficiency, tail call elimination is important in the functional programming idiom known as continuation-passing style (CPS), which would otherwise quickly run out of stack space.

Syntactic form[ edit ]

A tail call can be located just before the syntactical end of a subroutine:

function foo(data)  a(data); return b(data);

Here, both a(data) and b(data) are calls, but b is the last thing the procedure executes before returning and is thus in tail position. However, not all tail calls are necessarily located at the syntactical end of a subroutine:

function bar(data)  if ( a(data) )  return b(data);  return c(data);

Here, both calls to b and c are in tail position. This is because each of them lies in the end of if-branch respectively, even though the first one is not syntactically at the end of bar‘s body.

In this code:

function foo1(data)  return a(data) + 1;
function foo2(data)  var ret = a(data); return ret;
function foo3(data)  var ret = a(data); return (ret == 0) ? 1 : ret;

the call to a(data) is in tail position in foo2, but it is not in tail position either in foo1 or in foo3, because control must return to the caller to allow it to inspect or modify the return value before returning it.

Example programs[ edit ]

The following program is an example in Scheme : [7]

;; factorial : number -> number;; to calculate the product of all positive;; integers less than or equal to n.(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))

This is not written in a tail recursion style, because the multiplication function (“*”) is in the tail position. This can be compared to:

;; factorial : number -> number;; to calculate the product of all positive;; integers less than or equal to n.(define (factorial n) (fact-iter 1 n))(define (fact-iter product n) (if (< n 2) product (fact-iter (* product n) (- n 1))))

This program assumes applicative-order evaluation. The inner procedure fact-iter calls itself last in the control flow. This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this: [7]

 call factorial (4) call fact-iter (1 4) call fact-iter (4 3) call fact-iter (12 2) call fact-iter (24 1) return 24 return 24 return 24 return 24 return 24

into the more efficient variant, in terms of both space and time:

 call factorial (4) call fact-iter (1 4) replace arguments with (4 3) replace arguments with (12 2) replace arguments with (24 1) return 24 return 24

This reorganization saves space because no state except for the calling function’s address needs to be saved, either on the stack or on the heap, and the call stack frame for fact-iter is reused for the intermediate results storage. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. In typical implementations, the tail recursive variant will be substantially faster than the other variant, but only by a constant factor.

Some programmers working in functional languages will rewrite recursive code to be tail-recursive so they can take advantage of this feature. This often requires addition of an “accumulator” argument (product in the above example) to the function. In some cases (such as filtering lists) and in some languages, full tail recursion may require a function that was previously purely functional to be written such that it mutates references stored in other variables.[ citation needed ]

Tail recursion modulo cons[ edit ]

Tail recursion modulo cons is a generalization of tail recursion optimization introduced by David H. D. Warren [8] in the context of compilation of Prolog , seen as an explicitly set once language. It was described (though not named) by Daniel P. Friedman and David S. Wise in 1974 [9] as a LISP compilation technique. As the name suggests, it applies when the only operation left to perform after a recursive call is to prepend a known value in front of a list returned from it (or to perform a constant number of simple data-constructing operations, in general). This call would thus be a tail call save for (” modulo “) the said cons operation. But prefixing a value at the start of a list on exit from a recursive call is the same as appending this value at the end of the growing list on entry into the recursive call, thus building the list as a side effect , as if in an implicit accumulator parameter. The following Prolog fragment illustrates the concept:

Prolog example[ edit ]

% tail recursive modulo cons:partition([], _, [], []).partition([X|Xs], Pivot, [X|Rest], Bigs) :- X @< Pivot, !, partition(Xs, Pivot, Rest, Bigs).partition([X|Xs], Pivot, Smalls, [X|Rest]) :- partition(Xs, Pivot, Smalls, Rest).
-- In Haskell, guarded recursion:partition :: Ord a => [a] -> a -> ([a],[a])partition [] _ = ([],[])partition (x:xs) p | x < p = (x:a,b) | otherwise = (a,x:b) where (a,b) = partition xs p
% With explicit unifications:% non-tail recursive translation:partition([], _, [], []).partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs], ( X @< Pivot -> partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest] ; partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest] ).
% With explicit unifications:% tail recursive translation:partition([], _, [], []).partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs], ( X @< Pivot -> Smalls=[X|Rest], partition(Xs,Pivot,Rest,Bigs) ; Bigs=[X|Rest], partition(Xs,Pivot,Smalls,Rest) ).

Thus in tail recursive translation such a call is transformed into first creating a new list node and setting its first field, and then making a tail call with the pointer to the node’s rest field as argument, to be filled recursively.

C example[ edit ]

The following fragment defines a recursive function in C that duplicates a linked list:

struct list void *value;struct list *next;;typedef struct list list;list *duplicate(const list *ls) list *head = NULL; if (ls != NULL)  list *p = duplicate(ls->next); head = malloc(sizeof *head); head->value = ls->value; head->next = p;  return head;
;; in Scheme,(define (duplicate ls) (if (not (null? ls)) (cons (car ls) (duplicate (cdr ls))) '()))
%% in Prolog,dup([X|Xs],R):- dup(Xs,Ys), R=[X|Ys].dup([],[]).

In this form the function is not tail-recursive, because control returns to the caller after the recursive call duplicates the rest of the input list. Even if it were to allocate the head node before duplicating the rest, it would still need to plug in the result of the recursive call into the next field after the call. [a]
So the function is almost tail-recursive. Warren’s method pushes the responsibility of filling the next field into the recursive call itself, which thus becomes tail call:

struct list void *value;struct list *next;;typedef struct list list;void duplicate_aux(const list *ls, list *end);list *duplicate(const list *ls) list head; duplicate_aux(ls, &head); return head.next;void duplicate_aux(const list *ls, list *end) if (ls != NULL)  end->next = malloc(sizeof *end); end->next->value = ls->value; duplicate_aux(ls->next, end->next);  else  end->next = NULL; 
;; in Scheme,(define (duplicate ls) (let ((head (list 1))) (let dup ((ls ls) (end head)) (cond  ((not (null? ls)) (set-cdr! end (list (car ls))) (dup (cdr ls) (cdr end))))) (cdr head)))
%% in Prolog,dup([X|Xs],R):- R=[X|Ys], dup(Xs,Ys).dup([],[]).

(A sentinel head node is used to simplify the code.) The callee now appends to the end of the growing list, rather than have the caller prepend to the beginning of the returned list. The work is now done on the way forward from the list’s start, before the recursive call which then proceeds further, instead of backward from the list’s end, after the recursive call has returned its result. It is thus similar to the accumulating parameter technique, turning a recursive computation into an iterative one.

Characteristically for this technique, a parent frame is created on the execution call stack, which the tail-recursive callee which can reuse as its own call frame if the tail-call optimization is present.

The tail-recursive implementation can now be converted into an explicitly iterative form, as an accumulating loop :

struct list void *value;struct list *next;;typedef struct list list;list *duplicate(const list *ls) list head, *end; end = &head; while (ls != NULL)  end->next = malloc(sizeof *end); end->next->value = ls->value; ls = ls->next; end = end->next;  end->next = NULL; return head.next;
 ;; in Scheme, (define (duplicate ls) (let ((head (list 1))) (do ((end head (cdr end)) (ls ls (cdr ls ))) ((null? ls) (cdr head)) (set-cdr! end (list (car ls))))))
%% in Prolog,%% N/A

History[ edit ]

In a paper delivered to the ACM conference in Seattle in 1977, Guy L. Steele summarized the debate over the GOTO and structured programming , and observed that procedure calls in the tail position of a procedure can be best treated as a direct transfer of control to the called procedure, typically eliminating unnecessary stack manipulation operations. [1] Since such “tail calls” are very common in Lisp , a language where procedure calls are ubiquitous, this form of optimization considerably reduces the cost of a procedure call compared to other implementations. Steele argued that poorly implemented procedure calls had led to an artificial perception that the GOTO was cheap compared to the procedure call. Steele further argued that “in general procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions”, with the machine code stack manipulation instructions “considered an optimization (rather than vice versa!)”. [1] Steele cited evidence that well optimized numerical algorithms in Lisp could execute faster than code produced by then-available commercial Fortran compilers because the cost of a procedure call in Lisp was much lower. In Scheme , a Lisp dialect developed by Steele with Gerald Jay Sussman , tail call elimination is guaranteed to be implemented in any interpreter. [10]

Implementation methods[ edit ]

Tail recursion is important to some high-level languages , especially functional and logic languages and members of the Lisp family. In these languages, tail recursion is the most commonly used way (and sometimes the only way available) of implementing iteration. The language specification of Scheme requires that tail calls are to be optimized so as not to grow the stack. Tail calls can be made explicitly in Perl , with a variant of the “goto” statement that takes a function name: goto &NAME; [11]

However, for language implementations which store function arguments and local variables on a call stack (which is the default implementation for many languages, at least on systems with a hardware stack , such as the x86 ), implementing generalized tail call optimization presents an issue: if the size of the callee’s activation record is different from that of the caller, then additional cleanup or resizing of the stack frame may be required. For these cases, optimizing tail recursion remains trivial, but general tail call optimization may be harder to implement efficiently.

For example, in the Java virtual machine (JVM), tail-recursive calls can be eliminated (as this reuses the existing call stack), but general tail calls cannot be (as this changes the call stack). [12] [13] As a result, functional languages such as Scala that target the JVM can efficiently implement direct tail recursion, but not mutual tail recursion.

The GCC , LLVM/Clang , and Intel compiler suites perform tail call optimization for C and other languages at higher optimization levels or when the -foptimize-sibling-calls option is passed. [14] [15] [16] Though the given language syntax may not explicitly support it, the compiler can make this optimization whenever it can determine that the return types for the caller and callee are equivalent, and that the argument types passed to both function are either the same, or require the same amount of total storage space on the call stack. [17]

Various implementation methods are available.

In assembly[ edit ]

This section does not cite any sources . Please help improve this section by adding citations to reliable sources . Unsourced material may be challenged and removed . (June 2014) ( Learn how and when to remove this template message )

Tail calls are often optimized by interpreters and compilers of functional programming and logic programming languages to more efficient forms of iteration . For example, Scheme programmers commonly express while loops as calls to procedures in tail position and rely on the Scheme compiler or interpreter to substitute the tail calls with more efficient jump instructions. [18]

For compilers generating assembly directly, tail call elimination is easy: it suffices to replace a call opcode with a jump one, after fixing parameters on the stack.
From a compiler’s perspective, the first example above is initially translated into pseudo- assembly language (in fact, this is valid x86 assembly ):

 foo: call B call A ret

Tail call elimination replaces the last two lines with a single jump instruction:

 foo: call B jmp A

After subroutine A completes, it will then return directly to the return address of foo, omitting the unnecessary ret statement.

Typically, the subroutines being called need to be supplied with parameters . The generated code thus needs to make sure that the call frame for A is properly set up before jumping to the tail-called subroutine. For instance, on platforms where the call stack does not just contain the return address , but also the parameters for the subroutine, the compiler may need to emit instructions to adjust the call stack. On such a platform, for the code:

function foo(data1, data2) B(data1) return A(data2)

(where data1 and data2 are parameters) a compiler might translate that as: [b]

 1  foo: 2  mov reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register. 3  push reg ; put data1 on stack where B expects it 4  call B ; B uses data1 5  pop ; remove data1 from stack 6  mov reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register. 7  push reg ; put data2 on stack where A expects it 8  call A ; A uses data2 9  pop ; remove data2 from stack.10  ret

A tail call optimizer could then change the code to:

1  foo:2  mov reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.3  push reg ; put data1 on stack where B expects it4  call B ; B uses data15  pop ; remove data1 from stack6  mov reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.7  mov [sp+data1],reg ; put data2 where A expects it8  jmp A ; A uses data2 and returns immediately to caller.

This code is more efficient both in terms of execution speed and use of stack space.

Through trampolining[ edit ]

Since many Scheme compilers use C as an intermediate target code, the tail recursion must be encoded in C without growing the stack, even if the C compiler does not optimize tail calls. Many implementations achieve this by using a device known as a trampoline , a piece of code that repeatedly calls functions. All functions are entered via the trampoline. When a function has to tail-call another, instead of calling it directly and then returning the result, it returns the address of the function to be called and the call parameters back to the trampoline (from which it was called itself), and the trampoline takes care of calling this function next with the specified parameters. This ensures that the C stack does not grow and iteration can continue indefinitely.

It is possible to implement trampolines using higher-order functions in languages that support them, such as Groovy , Visual Basic .NET and C# . [19]

Using a trampoline for all function calls is rather more expensive than the normal C function call, so at least one Scheme compiler, Chicken , uses a technique first described by Henry Baker from an unpublished suggestion by Andrew Appel , [20] in which normal C calls are used but the stack size is checked before every call. When the stack reaches its maximum permitted size, objects on the stack are garbage-collected using the Cheney algorithm by moving all live data into a separate heap. Following this, the stack is unwound (“popped”) and the program resumes from the state saved just before the garbage collection. Baker says “Appel’s method avoids making a large number of small trampoline bounces by occasionally jumping off the Empire State Building.” [20] The garbage collection ensures that mutual tail recursion can continue indefinitely. However, this approach requires that no C function call ever returns, since there is no guarantee that its caller’s stack frame still exists; therefore, it involves a much more dramatic internal rewriting of the program code: continuation-passing style .

Relation to while construct[ edit ]

Tail recursion can be related to the while control flow operator by means of a transformation such as the following:

function foo(x) is: if predicate(x) then return foo(bar(x)) else return baz(x)

The above construct transforms to:

function foo(x) is: while predicate(x) do: x ← bar(x) return baz(x)

In the preceding, x may be a tuple involving more than one variable: if so, care must be taken in designing the assignment statement x ← bar(x) so that dependencies are respected. One may need to introduce auxiliary variables or use a swap construct.

More general uses of tail recursion may be related to control flow operators such as break and continue, as in the following:

function foo(x) is: if p(x) then return bar(x) else if q(x) then return baz(x) ... else if t(x) then return foo(quux(x)) ... else return foo(quuux(x))

where bar and baz are direct return calls, whereas quux and quuux involve a recursive tail call to foo. A translation is given as follows:

function foo(x) is: do: if p(x) then x ← bar(x) break else if q(x) then x ← baz(x) break ... else if t(x) then x ← quux(x) continue ... else x ← quuux(x) continue loop return x

By language[ edit ]

  • Common Lisp – Some implementations perform tail-call optimization during compilation if optimizing for speed
  • JavaScript – ECMAScript 6.0 compliant engines should have tail calls [21] which is now implemented on Safari / WebKit [22]
  • Lua – Tail recursion is performed by the reference implementation [23]
  • Python – Stock Python implementations do not perform tail-call optimization, though a third-party module is available to do this. [24] Language inventor Guido van Rossum contends that stack traces are altered by tail call elimination making debugging harder, and prefers that programmers use explicit iteration instead [25]
  • Scheme – Required by the language definition [26] [27]
  • Racket – Yes.
  • Tcl – Since Tcl 8.6, Tcl has a tailcall command [28]
  • Kotlin – Has tailrec modifier for functions [29]
  • Elixir – Elixir implements tail-call optimization [30] As do all languages currently targeting the BEAM VM.
  • Perl – Explicit with a variant of the “goto” statement that takes a function name: goto &NAME; [31]
  • Scala – Tail recursive functions are automatically optimized by the compiler. Such functions can also optionally be marked with a @tailrec annotation.
  • Objective-C – Compiler optimizes tail calls when -O1 (or higher) option specified but it is easily disturbed by calls added by ARC .
  • F# – F# implements TCO by default where possible “Tail Calls in F#” . msdn. Microsoft.

    ]

See also[ edit ]

  • icon Computer programming portal
Look up tail recursion in Wiktionary, the free dictionary.
  • Course-of-values recursion
  • Recursion (computer science)
  • Inline expansion
  • Leaf subroutine
  • Corecursion

Notes[ edit ]

  1. ^ Like this:
    if (ls != NULL)  head = malloc( sizeof *head); head->value = ls->value; head->next = duplicate( ls->next); 

  2. ^ The call instruction first pushes the current code location onto the stack and then performs an unconditional jump to the code location indicated by the label. The ret instruction first pops a code location off the stack, then performs an unconditional jump to the retrieved code location.

References[ edit ]

  1. ^ a b c Steele, Guy Lewis (1977). “Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO”. Proceedings of the 1977 annual conference on – ACM ’77. pp. 153–162. doi : 10.1145/800179.810196 . hdl : 1721.1/5753 . ISBN   978-1-4503-2308-6 .
  2. ^ “The LLVM Target-Independent Code Generator — LLVM 7 documentation” . llvm.org.
  3. ^ “recursion – Stack memory usage for tail calls – Theoretical Computer Science” . Cstheory.stackexchange.com. 2011-07-29. Retrieved 2013-03-21.
  4. ^ a b “Revised^6 Report on the Algorithmic Language Scheme” . R6rs.org. Retrieved 2013-03-21.
  5. ^ “Revised^6 Report on the Algorithmic Language Scheme – Rationale” . R6rs.org. Retrieved 2013-03-21.
  6. ^ “Revised^6 Report on the Algorithmic Language Scheme” . R6rs.org. Retrieved 2013-03-21.
  7. ^ a b Sussman, G. J.; Abelson, Hal (1984). Structure and Interpretation of Computer Programs. Cambridge, MA: MIT Press. ISBN   0-262-01077-1 .
  8. ^ D. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980.
  9. ^ Daniel P. Friedman and David S. Wise, Technical Report TR19: Unwinding Structured Recursions into Iterations , Indiana University, Dec. 1974.
  10. ^ R5RS Sec. 3.5, Richard Kelsey; William Clinger; Jonathan Rees; et al. (August 1998). “Revised5 Report on the Algorithmic Language Scheme” . Higher-Order and Symbolic Computation. 11 (1): 7–105. doi : 10.1023/A:1010051815785 .
  11. ^ Contact details. “goto” . perldoc.perl.org. Retrieved 2013-03-21.
  12. ^ ” What is difference between tail calls and tail recursion? “, Stack Overflow
  13. ^ ” What limitations does the JVM impose on tail-call optimization “, Programmers Stack Exchange
  14. ^ Lattner, Chris. “LLVM Language Reference Manual, section: The LLVM Target-Independent Code Generator, sub: Tail Call Optimization” . The LLVM Compiler Infrastructure. The LLVM Project. Retrieved 24 June 2018.
  15. ^ “Using the GNU Compiler Collection (GCC): Optimize Options” . gcc.gnu.org.
  16. ^ “foptimize-sibling-calls” . software.intel.com.
  17. ^ “Tackling C++ Tail Calls” .
  18. ^ Probst, Mark (20 July 2000). “proper tail recursion for gcc” . GCC Project. Retrieved 10 March 2015.
  19. ^ Samuel Jack, Bouncing on your tail . Functional Fun. April 9, 2008.
  20. ^ a b Henry Baker, “CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A.”
  21. ^ Beres-Deak, Adam. “Worth watching: Douglas Crockford speaking about the new good parts of JavaScript in 2014” . bdadam.com.
  22. ^ “ECMAScript 6 in WebKit” . 13 October 2015.
  23. ^ “Lua 5.2 Reference Manual” . www.lua.org.
  24. ^ “baruchel/tco” . GitHub.
  25. ^ Rossum, Guido Van (22 April 2009). “Neopythonic: Tail Recursion Elimination” .
  26. ^ “Revised^5 Report on the Algorithmic Language Scheme” . www.schemers.org.
  27. ^ “Revised^6 Report on the Algorithmic Language Scheme” . www.r6rs.org.
  28. ^ “tailcall manual page – Tcl Built-In Commands” . www.tcl.tk.
  29. ^ “Functions: infix, vararg, tailrec – Kotlin Programming Language” . Kotlin.
  30. ^ “Recursion” . elixir-lang.github.com.
  31. ^ “goto – perldoc.perl.org” . perldoc.perl.org.

This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the “relicensing” terms of the GFDL , version 1.3 or later.

Retrieved from ” https://en.wikipedia.org/w/index.php?title=Tail_call&oldid=871620799 ”
Categories :

  • Programming language implementation
  • Implementation of functional programming languages
  • Subroutines
  • Control flow
  • Recursion
  • Scheme (programming language)
  • Articles with example Scheme code
Hidden categories:

  • All articles with unsourced statements
  • Articles with unsourced statements from April 2007
  • Articles needing additional references from June 2014
  • All articles needing additional references
  • Articles with example C code

Navigation menu

Personal tools

  • Not logged in
  • Talk
  • Contributions
  • Create account
  • Log in

Namespaces

  • Article
  • Talk

Variants

    Views

    • Read
    • Edit
    • View history

    More


      Navigation

      • Main page
      • Contents
      • Featured content
      • Current events
      • Random article
      • Donate to Wikipedia
      • Wikipedia store

      Interaction

      • Help
      • About Wikipedia
      • Community portal
      • Recent changes
      • Contact page

      Tools

      • What links here
      • Related changes
      • Upload file
      • Special pages
      • Permanent link
      • Page information
      • Wikidata item
      • Cite this page

      Print/export

      • Create a book
      • Download as PDF
      • Printable version

      Languages

      • Čeština
      • Deutsch
      • Français
      • 한국어
      • עברית
      • Lietuvių
      • Nederlands
      • 日本語
      • Polski
      • Русский
      • Српски / srpski
      • Suomi
      • Svenska
      • Türkçe
      • Українська
      • 中文
      Edit links

      • This page was last edited on 2 December 2018, at 09:50 (UTC).
      • Text is available under the Creative Commons Attribution-ShareAlike License ;
        additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy . Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. , a non-profit organization.
      • Privacy policy
      • About Wikipedia
      • Disclaimers
      • Contact Wikipedia
      • Developers
      • Cookie statement
      • Mobile view
      • Wikimedia Foundation
      • Powered by MediaWiki