The Windward Studio

Windward Blog Home

When You Should Use Tail-End Recursion

by
Posted on 08/20/2014

Please Share This

 

Want to speed up your code or you’re struggling with stack overflows? Often, refactoring a recursive loop into an iterative one is impossible.

In these cases, you may find tail-end recursion to be useful. If implemented properly (and of course, provided your programming language supports it), your code will be optimized to be approximately as fast as an iterative loop.

Tail-Call Optimization

To understand tail-end recursion, first it helps to know about tail-call optimization.

Tail-call optimization involves changing your code so that it doesn’t push variables that will not be used again onto the stack; the initial parameters of a recursive function will never be used again and don’t need to take extra time or stack-space. Tail-call optimization avoids allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function.

The most common use for this optimization is in tail-end recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.

A Simple Example

To better understand, let’s go over a simple example of tail-call optimization. We’ll be using Python, which supports tail-end recursion.

First, an example without tail-call-optimization:

If you called sum_recursively (5), this is what Python would actually evaluate:

 

To improve performance or solve stack overflow problems, you can refactor this function. Here is the same function refactored to use tail-end recursion:

 

Now if you call this function with a parameter of 5:

 

See how in this example old variables are no longer required to compute the final result? This allows for Python to use less memory and no longer have to push those variables onto the stack.

Tail-End Recursion

Great – so we get tail-call optimization. But what is tail-end recursion?

In languages that support it, it is a compile-time-optimization that uses goto. The above tail_end_sum is turned into the following (of course, this is pseudo code, as goto/label doesn’t exist in python) by the Python compiler:

 

While nothing is perfect, you can see from this example that tail-end recursion is a great route if refactoring a recursive loop won’t work. Many programmers don’t use tail-end recursion, often due to lack of familiarity, but I encourage you to take a look.

Questions? Ask in The Windward Studio Blog!

Please Share This



Author: Nathan Bellowe

Nathan is a Development Intern at Windward. He spends most of his time working in C#, Java, and lately Javascript. He studies computer science but continues his work at Windward while in school. He plans to continue working on Windward, and aims to be the chief Robot Engineer, when the company follows the inevitable path from reporting software to robots, unless he breaks his hands (like he’s done with both feet this summer), and then he won’t be able to code.

Other posts by