When You Should Use TailEnd Recursion 

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 tailend 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.
TailCall Optimization
To understand tailend recursion, first it helps to know about tailcall optimization.
Tailcall 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 stackspace. Tailcall 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 tailend recursion, where a recursive function written to take advantage of tailcall optimization can use constant stack space.
A Simple Example
To better understand, let’s go over a simple example of tailcall optimization. We’ll be using Python, which supports tailend recursion.
First, an example without tailcalloptimization:
1 2 3 4 5 6 7 8 9 10 11 12 
def sum_recursively(x): if x == 1: return x else: return x + sum_recursively(x  1) 
If you called sum_recursively (5), this is what Python would actually evaluate:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
sum_recursively (5) 5 + sum_recursively (4) 5 + (4 + sum_recursively (3)) 5 + (4 + (3 + sum_recursively (2))) 5 + (4 + (3 + (2 + sum_recursively (1)))) 5 + (4 + (3 + (2 + 1))) // many different variables are now being kept in memory! 
To improve performance or solve stack overflow problems, you can refactor this function. Here is the same function refactored to use tailend recursion:
1 2 3 4 5 6 7 8 9 10 11 12 
def tail_end_sum(x, running_total=0): if x == 0: return running_total else: return tail_end_sum (x  1, running_total + x) //by only returning the result of the function call, extra memory isn’t being used 
Now if you call this function with a parameter of 5:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
tail_end_sum (5, 0) //the compiler says: “Oh, the next parameters are going to be 51, and 0+5, so this is the same thing as: ” tail_end_sum (4, 5) // the next one is going to be: (41, 5+4) tail_end_sum (3, 9) // the next one is going to be: (31, 9+3) tail_end_sum (2, 12) // the next one is going to be: (21, 12+2) tail_end_sum (1, 14) // the next one is going to be: (11, 14+1) tail_end_sum (0, 15) // == 15 
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.
TailEnd Recursion
Great – so we get tailcall optimization. But what is tailend recursion?
In languages that support it, it is a compiletimeoptimization 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
def tail_end_sum(x, running_total=0): label: if x == 0: return running_total else: runningtotal += x; x = x1; goto label; 
While nothing is perfect, you can see from this example that tailend recursion is a great route if refactoring a recursive loop won’t work. Many programmers don’t use tailend recursion, often due to lack of familiarity, but I encourage you to take a look.
Questions? Ask in The Windward Studio Blog!
Author: Nathan BelloweNathan 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 Nathan Bellowe 