How does tail recursion really help over traditional recursion?

Question

I was reading up about the difference between tail recursion and Traditional recursion and find it mentioned that "Tail Recursion however is a form of recursion that doesn’t use any stack space, and thus is a way to use recursion safely."'

I am struggling to understand how.

Comparing finding factorial of a number using the Traditional and tail recursion

Traditional recursion

/* traditional recursion */
fun(5);


int fun(int n)
{
 if(n == 0)
  return 1;


 return n * fun(n-1);
}

Here, the call stack would look like

5 * fact(4)
      |
   4 * fact(3)
          |
       3 * fact(2)
             |
         2 * fact(1)
               |
            1 * fact(0)
                  |
                  1

Tail recursion

/* tail recursion */
fun(5,1)


int fun(int n, int sofar)
{
 int ret = 0;


 if(n == 0)
  return sofar;


 ret = fun(n-1,sofar*n);


 return ret;
}

However, even here, the variable 'sofar' would hold - 5,20,60,120,120 at different points. But once return is called from the base case which is recursive invocation #4, it still has to return 120 to recursive invocation #3, then to#2, #1 and back to main. So, I mean to say that the stack is used and everytime you return to the previous call, the variables at that point in time can be seen, which means it is being saved at each step.

Unless, the tail recursion was written like below, I am not being able to understand how it saves stack space.

/* tail recursion */
fun(5,1)

int fun(int n, int sofar)
{
 int ret = 0;


 if(n == 0)
  return 'sofar' back to main function, stop recursing back; just a one-shot return


 ret = fun(n-1,sofar*n);


 return ret;
}

PS : I have read few threads on SO and came to understand what tail recursion is, however, this question is more related to why it saves stack space. I could not find a similar question where this was discussed.

You are confused on what is tail recursion. see this: http://stackoverflow.com/questions/2693683/tail-recursion-in-c — NathanOliver, Jul 02 '15 at 18:00
I wonder about the phrase. I just know tail-chaining, which just jumps to `f` if used like `return f()`, instead of creating a new stack-frame, calling `F()` and returning the result. If tail-chained, `f()` then returns directly to the original caller. However, that is a matter of compiler optimization; you should rely on that. The compiler might have very well a different idea how/if to tail-chain. — too honest for this site, Jul 02 '15 at 18:10
tail recursion is traditional recursion. Or rather, it is one form of recursion; but it is probably the most traditional of all the forms. See, eg., https://en.wikipedia.org/wiki/Recursion#Recursively_defined_sets: translated into pseudo-code, it might be: `def is_in_N(x): if x == 0 then return true else return is_in_N(x-1)` — rici, Jul 02 '15 at 19:47
A tail call is needed to be able to tail call optimize it but a tail call in itself does not guarantee optimization. With a language like Scheme which has TCO as a requirement it's no trouble and you can say tail recursion does not use additional stack space, but for all other languages which does ot require it tail recursion it itelf does not mean you won't use stack. C++ is in that catergory. a function that only do tail calls is an iterative **process**, while recursion where at least one call is not in tail position is a recursive process. It has nothing to do with tradition. — Sylwester, Jul 03 '15 at 00:35

rodrigo · Accepted Answer · 2015-07-02T18:13:54.693

The trick is that if the compiler notices the tail recursion, it can compile a goto instead. It will generate something like the following code:

int fun_optimized(int n, int sofar)
{
start:
    if(n == 0)
       return sofar;

    sofar = sofar*n;
    n = n-1;
    goto start;
}

And as you can see, the stack space is reused for each iteration.

Note that this optimization can only be done if the recursive call is the very last action in the function, that is tail recursion (try doing it manually to the non-tail case and you'll see that's just impossible).

haccks · Answer 2 · 2016-07-28T12:10:54.703

A function call is tail recursive when function call (recursive) is performed as final action. Since the current recursive instance is done executing at that point, no need to maintaining its stack frame.

In this case, creating a stack frame on top of the current stack frame is nothing more than waste.
When compiler recognizes a recursion to be a tail recursion then it does not create nesting stack frames for each of the call instead it use the current stack frame. This is equivalent in effect to a goto statement. This make make that function call iterative rather recursive.

Note that in traditional recursion, every recursive call must have to complete before compiler performing the multiplication operations:

fun(5)
5 * fun(4)
5 * (4 * fun(3))
5 * (4 * (3 * fun(2)))
5 * (4 * (3 * (2 * fun(1))))
5 * (4 * (3 * (2 * 1)))
120

Nested stack frame needed in this case. Look at wiki for more information.

In case of tail recursion, with each call of fun, variable sofar is updated:

fun(5, 1)
fun(4, 5)
fun(3, 20)
fun(2, 60)
fun(1, 120)
120

No need to save stack frame of current recursive call.

How does tail recursion really help over traditional recursion?

2 Answers2