What is tail recursion

Question

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

User · Answer

The recursive function is a function which calls by itself

It allows programmers to write efficient programs using a minimal amount of code.

The downside is that they can cause infinite loops and other unexpected results if not written properly.

I will explain both Simple Recursive function and Tail Recursive function

In order to write a Simple recursive function

The first point to consider is when should you decide on coming out of the loop which is the if loop
The second is what process to do if we are our own function

From the given example:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

From the above example

if(n <=1)
     return 1;

Is the deciding factor when to exit the loop

else 
     return n * fact(n-1);

Is the actual processing to be done

Let me the break the task one by one for easy understanding.

Let us see what happens internally if I run fact(4)

Substituting n=4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If loop fails so it goes to else loop so it returns 4 * fact(3)

In stack memory, we have 4 * fact(3)

Substituting n=3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If loop fails so it goes to else loop

so it returns 3 * fact(2)

Remember we called ```4 * fact(3)``

The output for fact(3) = 3 * fact(2)

So far the stack has 4 * fact(3) = 4 * 3 * fact(2)

In stack memory, we have 4 * 3 * fact(2)

Substituting n=2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If loop fails so it goes to else loop

so it returns 2 * fact(1)

Remember we called 4 * 3 * fact(2)

The output for fact(2) = 2 * fact(1)

So far the stack has 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

In stack memory, we have 4 * 3 * 2 * fact(1)

Substituting n=1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If loop is true

so it returns 1

Remember we called 4 * 3 * 2 * fact(1)

The output for fact(1) = 1

So far the stack has 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Finally, the result of fact(4) = 4 * 3 * 2 * 1 = 24

The Tail Recursion would be

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

Substituting n=4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If loop fails so it goes to else loop so it returns fact(3, 4)

In stack memory, we have fact(3, 4)

Substituting n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If loop fails so it goes to else loop

so it returns fact(2, 12)

In stack memory, we have fact(2, 12)

Substituting n=2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If loop fails so it goes to else loop

so it returns fact(1, 24)

In stack memory, we have fact(1, 24)

Substituting n=1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If loop is true

so it returns running_total

The output for running_total = 24

Finally, the result of fact(4,1) = 24

User · Answer

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

User · Answer

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

User · Answer

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 1      if  x    1       return fac     else      return factorial x-1  x fac       The initial call to factorial would be factorial n  where fac 1  default value  and n is the number for which the factorial is to be calculated

User · Answer

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

User · Answer

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

User · Answer

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  lt   n         k    i        i        return k      is equivalent to the tail-recursive function s   sum aux n i k      if  i  lt   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

User · Answer

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

User · Answer

Consider a simple function that adds the first N natural numbers   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 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

User · Answer

Many people have already explained recursion here  I would like to cite a couple of thoughts about some advantages that recursion gives from the book    Concurrency in  NET  Modern patterns of concurrent and parallel programming    by Riccardo Terrell           Functional recursion is the natural way to iterate in FP because it   avoids mutation of state  During each iteration  a new value is passed   into the loop constructor instead to be updated  mutated   In   addition  a recursive function can be composed  making your program   more modular  as well as introducing opportunities to exploit   parallelization     Here also are some interesting notes from the same book about tail recursion      Tail-call recursion is a technique that converts a regular recursive   function into an optimized version that can handle large inputs   without any risks and side effects         NOTE The primary reason for a tail call as an optimization is to   improve data locality  memory usage  and cache usage  By doing a tail   call  the callee uses the same stack space as the caller  This reduces   memory pressure  It marginally improves the cache because the same   memory is reused for subsequent callers and can stay in the cache    rather than evicting an older cache line to make room for a new cache   line

User · Answer

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

User · 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     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

User · Answer

A function is tail recursive if each recursive case consists only of a call to the function itself  possibly with different arguments   Or  tail recursion is recursion with no pending work   Note that this is a programming-language independent concept  Consider the function defined as  g a  b  n    a   b n  A possible tail-recursive formulation is  g a  b  n    n is zero   a              n is odd    g a b  b    n-1               otherwise   g a    b b  n 2   If you examine each RHS of g      that involves a recursive case  you ll find that the whole body of the RHS is a call to g       and only that   This definition is tail recursive  For comparison  a non-tail-recursive formulation might be  g  a  b  n    a   f b  n  f b  n    n is zero   1           n is odd    f b  n-1    b           otherwise   f b  n 2    2  Each recursive case in f      has some pending work that needs to happen after the recursive call  Note that when we went from g  to g  we made essential use of associativity  and commutativity  of multiplication   This is not an accident  and most cases where you will need to transform recursion to tail-recursion will make use of such properties  if we want to eagerly do some work rather than leave it pending  we have to use something like associativity to prove that the answer will be the same  Tail recursive calls can be implemented with a backwards jump  as opposed to using a stack for normal recursive calls   Note that detecting a tail call  or emitting a backwards jump is usually straightforward   However  it is often hard to rearrange the arguments such that the backwards jump is possible   Since this optimization is not free  language implementations can choose not to implement this optimization  or require opt-in by marking recursive calls with a  tailcall  instruction and or choosing a higher optimization setting  Some languages  e g  Scheme  do  however  require all implementations to optimize tail-recursive functions  maybe even all calls in tail position  Backwards jumps are usually abstracted as a  while  loop in most imperative languages  and tail-recursion  when optimized to a backwards jump  is isomorphic to looping

User · Answer

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

User · Answer

A tail recursive function is a recursive function where the last operation it does before returning is make the recursive function call  That is  the return value of the recursive function call is immediately returned  For example  your code would look like this   def recursiveFunction some params         some code here     return recursiveFunction some args        no code after the return statement   Compilers and interpreters that implement tail call optimization or tail call elimination can optimize recursive code to prevent stack overflows  If your compiler or interpreter doesn t implement tail call optimization  such as the CPython interpreter  there is no additional benefit to writing your code this way   For example  this is a standard recursive factorial function in Python   def factorial number       if number    1            BASE CASE         return 1     else            RECURSIVE CASE           Note that  number    happens  after  the recursive call            This means that this is  not  tail call recursion          return number   factorial number - 1    And this is a tail call recursive version of the factorial function   def factorial number  accumulator 1       if number    0            BASE CASE         return accumulator     else            RECURSIVE CASE           There s no code after the recursive call            This is tail call recursion          return factorial number - 1  number   accumulator  print factorial 5      Note that even though this is Python code  the CPython interpreter doesn t do tail call optimization  so arranging your code like this confers no runtime benefit    You may have to make your code a bit more unreadable to make use of tail call optimization  as shown in the factorial example   For example  the base case is now a bit unintuitive  and the accumulator parameter is effectively used as a sort of global variable    But the benefit of tail call optimization is that it prevents stack overflow errors   I ll note that you can get this same benefit by using an iterative algorithm instead of a recursive one    Stack overflows are caused when the call stack has had too many frame objects pushed onto  A frame object is pushed onto the call stack when a function is called  and popped off the call stack when the function returns  Frame objects contain info such as local variables and what line of code to return to when the function returns   If your recursive function makes too many recursive calls without returning  the call stack can exceed its frame object limit   The number varies by platform  in Python it is 1000 frame objects by default   This causes a stack overflow error   Hey  that s where the name of this website comes from    However  if the last thing your recursive function does is make the recursive call and return its return value  then there s no reason it needs to keep the current frame object needs to stay on the call stack  After all  if there s no code after the recursive function call  there s no reason to hang on to the current frame object s local variables  So we can get rid of the current frame object immediately rather than keep it on the call stack  The end result of this is that your call stack doesn t grow in size  and thus cannot stack overflow   A compiler or interpreter must have tail call optimization as a feature for it to be able to recognize when tail call optimization can be applied  Even then  you may have rearrange the code in your recursive function to make use of tail call optimization  and it s up to you if this potential decrease in readability is worth the optimization

User · Answer

Tail Recursion is pretty fast as compared to normal recursion  It is fast because the output of the ancestors call will not be written in stack to keep the track  But in normal recursion all the ancestor calls output written in stack to keep the track

User · Answer

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  amp optional  product 1        if  zerop n  product             1- n     product n       And then for fun you could try  format nil   R     25

User · Answer

It is a special form of recursion where the last operation of a function is a recursive call  The recursion may be optimized away by executing the call in the current stack frame and returning its result rather than creating a new stack frame  A recursive function is tail recursive when recursive call is the last thing executed by the function  For example the following C   function print   is tail recursive  An example of tail recursive function     void print int n      if  n  lt  0   return   cout  lt  lt   quot   quot   lt  lt  n   print n-1           The last executed statement is recursive call   The tail recursive functions considered better than non tail recursive functions as tail-recursion can be optimized by compiler  The idea used by compilers to optimize tail-recursive functions is simple  since the recursive call is the last statement  there is nothing left to do in the current function  so saving the current function   s stack frame is of no use

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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          The body of a lambda expression is a tail expression   If  if E0 E1 E2  is a tail expression  then both E1 and E2 are tail expressions    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

User · Answer

In Java  here s a possible tail recursive implementation of the Fibonacci function   public int tailRecursive final int n        if  n  lt   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  lt   2          return 1      return recursive n - 1    recursive n - 2

User · Answer

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  amp tail rec sum    throw away current stack frame

User · Answer

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

User · Answer

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

User · 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

[algorithm] What is tail recursion?

Examples related to algorithm

Examples related to language-agnostic

Examples related to functional-programming

Examples related to recursion

Examples related to tail-recursion