Tail Recursion

If we want the memory consumption of an iterative approach and the elegance of a recursive implementation, then we would need to take a look at : Tail recursion! So, let’s start decoding this.

In my previous blog on recursion, we noted the comparison between iterative and recursive implementations. Now, if we want the memory consumption of  an iterative approach and the elegance of a recursive implementation, then I had mentioned that we would need to take a look at : Tail recursion! So, let’s start decoding this.


What is Tail Recursion ?

Tail call refers to an operation where we call a function say, g() and immediately return it’s return value as the return value of our function f(). In this case, we will not  need to preserve any of the state of the current code (state of g()) – since we are just about to throw it away and return.

Tail recursion is a form of recursion where the recursive call (call to same procedure f() itself) is the absolute last operation performed (called recursive tail call). Basically, meaning that there is nothing left to execute in the function after recursive calls – ie., the function returns the result of a recursive call.

The result of recursive call in this case can be passed directly for extra computation,  instead of waiting for it , which translates to no extra stack space. Normal recursive call, on the other hand, has a stack frame allocated, so that the compiler remembers where to get back to and to have the necessary variable values ready after recursive call is finished. This optimization is called – tail call optimization (TCO).

To write tail recursive version of the function, it means that we need to make sure recursive call is the absolute last operation in the function – there should not be any extra operations performed after the recursive call.


Let’s consider a very simple example to understand this concept.

Example

Consider a recursive function that returns the sum of ‘n’ positive numbers.

I .Recursive implementation

  • The recursive formula for sum of “n” numbers is given by: sum(n) = n+sum(n-1)
  • and sum is 1 when input is 1. (base case)

int sum(int n)

{

// Base condition for input = 1.

if(n==1) {

return 1;

}

// cases greater than 1.

else {

return n+sum(n-1); //This has extra operation of adding “n” to sum returned from recursive  function call

}

}

II. Implementing tail recursive version

  • To re-write sum function above in tail recursive form, all we have to do is :
    1. Identify the extra operation performed between return and recursive call . In this case addition of “n” to what is returned from recursive call.
    2. Modify and re-write the function to do this extra operation internally and then return, usually involves passing extra state variable called accumulation.
    3. Retain only recursive function call as the last operation in the method.

Now, let’s give tail recursive implementation a shot using the three steps outlined above.

  • In the recursive implementation above (under I),  we can see that there is an extra operation of adding output of recursive call to “n” at the end as highlighted in red.
  • For step 1 : The last line in the implementation can be split and written as :
  • y = sum(n-1);  
  • result = n+ y ;  //
  • return result ; 

For steps 2/3 : The new function version will take an extra argument which is an accumulation of current value. So, the extra operation to be performed is taken care of in the function call itself and not after return from recursive function call. Note : This style of passing control explicitly is called “Continuous Passing Style“. This makes sure that recursive call is also the last operation performed.

r2


Role of Compiler

Modern compilers support tail call elimination for tail recursive functions- an optimization called “TCO” (Tail Call optimization) as briefly mentioned above. TCO is the process by which a compiler can make a call to a function and take no additional stack space. The only case this would happens is if the last instruction executed in a function f() is a call to a function g(). Of course, in recursive case the call will be to itself f().

I have personally programmed in C and Python. GCC compiler (C compiler) offers TCO (Tail call optimizations).

Essentially, when we re-write the function in tail recursive form, the compiler optimization looks like below. It would be converted to a goto instead of recursive calls with stack allocation for it to remember the outcome of each recursive call to be used for the extra operation. This means that we  will not hit the stack over flow problem. Yay!

int tail_recursive_sum(int n, int accum=0) {
label:
    if (n == 1) return n+accum;
    accum += n--;
    goto label;
}

However, python implementation does not support TCO internally, which means it is expected that we judge the depth of recursion and re-write the iterative version, if we want to be safe with stack usage.

Generally, the need for recursive call optimization is dependent on the performance of your algorithm. If you have to implement a program that takes O(n) operations, it is not a good idea to use recursive version, while if it is O(logn) like tree implementations, we should be okay using the recursive version, we may not blow up stack.

Of course, I have shown a simple example here. There may be more complicated use cases. May be I will write about them soon in another blog. 😉

I want to keep the tidbit entries concise !


Conclusion

  • The function executes a little faster, since no stack pushes and pops are required
  • Function recursion depth is not a constraint any more, as there is no linear growth of stack usage with recursive calls.
  • We will not hit the stack overflow issue with this implementation.

So, if you are coding in C , you could implement a tail recursive way to get the benefit of compiler TCO, while for python use the iterative version! :). That’s all for today !

Check this for more details on this topic w.r.t C++ as mentioned by John in the comments below.  I will need to catch up on this as well. So, until next time,  keep decoding !

  1. as a python coder, im disappointed. as a hobbyist, tutor, and language author im delighted! thanks, you already know i was looking forward to this one.

    Liked by 1 person

    Reply

    1. Hope this tidbit helped :).
      Yes! I am not really sure of why such a design choice was made for python. 🤔

      Liked by 1 person

      Reply

  2. One could read more of the background to this article in Guy Steele’s papers, and, if I remember, the one with Lambda: The Ultimate Goto in its title.

    Liked by 1 person

    Reply

    1. Hi John,
      Could you please link them here? Thank you 🙂

      Like

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: