What is a Tail Recursion?

Tail recursion is a type of programming method call where a method calls itself, then immediately returns the value of that second call. In other words, tail recursion occurs when the final statement inside a method is another call to that same method. The parameters in the second method call are generally different from those of the first, but this is not required. In order for this recursion to work, the method that is called within itself must return a concrete value, such as a number, string, or some other object. Void methods, which do not return a value, do not work well for recursion.

The requirement that a recursive call must be the last statement in its calling method does not necessarily mean that the recursive call is the last line in the method. A proper tail recursion call can also be found inside a control structure, which means that, in source code, the control structure may end the method rather than the call. The important distinction in this case is that a control structure is not a programming statement, but a built-in part of the computer language.

Tail recursion exists in many computer languages, including Java and C++. Frequently, these recursive calls can be rewritten using other means, such as for loops, while loops, or goto statements. The utility of recursion is found when creating many sequential calls to the same method. Recursion is often the cleanest and easiest way to accomplish repetitive tasks.

A common example of tail recursion is a method that calculates the factorial of a number. This process is ideal because, starting at any number, every number before it is multiplied together. So, to find the factorial of 5, the proper process to do that would be to multiply 5*4*3*2*1. The recursion comes in because of how the factorial method is structured: if the factorial is 1, return 1, otherwise return the factorial of the number given to the method minus one. This method is also useful because it can be equivalently written using either type of tail recursion, with or without a control statement around a final method call.

Tail recursion is just one example of the multiple types of recursion. The concept in all types of recursion is essentially the same, that in some fashion a method calls itself. Of these types, the distinction of tail recursion is that the value of a recursive call is immediately returned, and nothing else happens in the calling method after that call.