HomeTalks
 
  

Tail recursion

October 8, 2013

Let's start this one with a formal definition which we'll borrow from Wikipedia:

In computer science, a tail call is a subroutine call that happens inside another procedure as its final action; it may produce a return value which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If any call that a subroutine performs, such that it might eventually lead to this same subroutine being called again down the call chain, is in tail position, such a subroutine is said to be tail-recursive, which is a special case of recursion. Tail calls need not be recursive – the call can be to another function – but tail recursion is particularly useful, and often easier to handle in implementations.

Putting it in simpler terms: when you call a procedure as the final action of your own procedure (function, method, etc) you have a tail call. If that call happens to be called again down the call chain, it is tail-recursive.

This is all very interesting you might say, but why is this important? Well, this is important because these type of calls can be implemented without adding new stack frames to the call stack. That means that we don't need to fill up the call stack and eat up a lot a memory in the process. This is particularly relevant for functional languages (for example Erlang, Scala) where for and while loops don't exist and so recursion is mandatory.

As I am more of a hands on guy let's illustrate this with some examples to understand the concept. Let's use a recursive function by nature: factorial. Straight from it's definition , we can code as an Erlang function to calculate it (we'll borrow it from Learn You Some Erlang for great good!) :

fac(0) -> 1;
fac(N) when N > 0 -> N*fac(N-1).

Let's do a small trace for this function with 4 as an input:

fac(4) = 4 * fac(4 - 1)
= 4 * 3 * fac(3 - 1)
= 4 * 3 * 2 * fac(2 - 1)
= 4 * 3 * 2 * 1 * fac(1 - 1)
= 4 * 3 * 2 * 1 * 1
= 4 * 3 * 2 * 1
= 4 * 3 * 2
= 4 * 6
= 24

While this works fine for a small number like 4, as you can see there are quite a lot of fac calls. Imagine that for big numbers: we would be in trouble. Because the last call for this function involves a multiplication between a number a a recursive call to fac, a new stack frame has to be placed in the call stack so that at the end we can go back and multiply the results.

Let's try and change our function to be tail recursive. What that means is that we will implement it in a way that the same stack frame is used. And that can be achieve if the last last call of our function is only, you guessed it, a funciton. Let's see how it goes:

tail_fac(N) -> tail_fac(N,1).
tail_fac(0,Acc) -> Acc;
tail_fac(N,Acc) when N > 0 -> tail_fac(N-1,N*Acc).

Again, let's do a small trace and check what's happening:

tail_fac(4) = tail_fac(4,1)
tail_fac(4,1) = tail_fac(4-1, 4*1)
tail_fac(3,4) = tail_fac(3-1, 3*4)
tail_fac(2,12) = tail_fac(2-1, 2*12)
tail_fac(1,24) = tail_fac(1-1, 1*24)
tail_fac(0,24) = 24

Well, well, well! It seems that we don't need to fill up the call stack with new frames after all. And this is all pretty with functional languages, but what about imperative one's? Let's make use a Python example.

def fac(n):
if n == 0:
return 1
else:
return n * fac(n-1)

Again, straight from the definition, and fairly simple. If we try to run with numbers bigger than 998 we get:

RuntimeError: maximum recursion depth exceeded

This is because Python, as well as other languages, has a limit (Python's default is 1000) to the number of recursive calls you can make. Faced with this, you can try and solve 3 ways:

  • increase the limit (you still would be limited to the maximum amount you could increase it to, and also would be increasing the calls stack size a lot and memory consumption
  • write an imperative alternative
  • write a tail recursive alternative

Because we're illustrating tail recursion, let's go with the third approach:

def fac(n):
return tail_fac(n, 1)
def tail_fac(n, acc):
if n == 0:
return acc
else:
return tail_fac(n - 1, acc * n)

If we try to run with numbers bigger than 998 the result will be:

RuntimeError: maximum recursion depth exceeded

Wait, what?!? How's this possible? I'm using a tail recursive solution. This shouldn't have happening. I've I been talking nonsense up until now? No I didn't, and I didn't choose Python by chance.

The fact is, although you might implement your function in a tail recursive fashion, it all comes down to the implementation of the language. The fact that the same stack frame is used for consecutive recursive calls depends on the language implementation. Python does not implement it. You can check the links bellow on, from Guido himself, explaining why:

P.S. I want to thank Ricardo Sousa and Nuno Silva for the reviews.

Ricardo Castro

Ricardo Castro

Software Engineering, DevOps, Taekwondo and Metal

 

 

© 2021