These days, I happened to talk about recursion with my friends. I suddenly found that many friends have a vague concept of "tail recursion". After searching online, I did not find any complete and detailed information. So I wrote such an article as a supplement to Internet information. :P
Recursion vs. Tail Recursion
I believe everyone is familiar with recursive operations. Simply put, a function calls itself directly or indirectly for recursion directly or indirectly. For example, we can use recursion to calculate the length of a one-way linked list:
public class Node
{
public Node(int value, Node next)
{
= value;
= next;
}
public int Value { get; private set; }
public Node Next { get; private set; }
}
Write a recursive GetLength method:
public static int GetLengthRecursively(Node head)
{
if (head == null) return 0;
return GetLengthRecursively() + 1;
}
When called, the GetLengthRecursively method will continue to call itself until it meets the recursive exit. Friends who have some knowledge of recursion will definitely guess that if the single necklace list is very long, then the above method may encounter stack overflow, that is, throwing a *Exception. This is because each thread is executing the code，Allocate a certain size of stack space（WindowsIn the system1M），Each time the method is called, a certain amount of information will be stored in the stack.（Such as parameters、Local variables、Return address, etc.），No matter how little this information is, it will take up a certain amount of space.，Thousands of such spaces accumulate，It naturally exceeds the stack space of the thread。 However, this problem is not unsolvable. We just need to change the recursion into the following form (in this article, we do not consider the non-recursive solution):
public static int GetLengthTailRecursively(Node head, int acc)
{
if (head == null) return acc;
return GetLengthTailRecursively(, acc + 1);
}
The GetLengthTailRecursively method has an additional acc parameter. The abbreviation of accumulator (accumulator). Its function is to "accumulate" the result of the call before "accumulating" during recursive call and pass it into the next recursive call - this is the biggest difference between the GetLengthTailRecursively method and the GetLengthRecursively method in recursive way: the GetLengthRecursive method needs to perform a "+1" after recursive call, and the GetLengthTailRecursively recursive call belongs to the last operation of the method. This is called "tail recursion". Compared with ordinary recursion, since the tail recursion call is at the end of the method, the various states accumulated by the method have no meaning to the recursive call result. Therefore, the data left in the method in this method can be completely cleared and the space is given to the last recursive call. Such optimization 1 allows recursion to not generate stacking on the call stack, meaning that instant "infinite" recursion will not overflow the stack. This is the advantage of tail recursion.
Some friends may have thought that the essence of tail recursion is actually to pass the "all states" required in the recursive method into the next call through the parameters of the method. For the GetLengthTailRecursively method, we need to give the initial value of the acc parameter when calling:
GetLengthTailRecursively(head, 0)
In order to further familiarize yourself with the use of tail recursion, we will use the famous "Fibonna" sequence as an example. The traditional recursion method is as follows:
public static int FibonacciRecursively(int n)
{
if (n < 2) return n;
return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
}
To transform it into tail recursion, we need to provide two accumulators:
public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
if (n == 0) return acc1;
return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}
Therefore, when calling, the initial values of two accumulators need to be provided:
FibonacciTailRecursively(10, 0, 1)
Tail recursion and Continuation
Continuation , that is, "things that need to be done" after "complete something". For example, the standard APM calling method in .NET is composed of the BeginXXX method and the EndXXX method, which is actually a kind of Continuation: after completing the BeginXXX method, the EndXXX method needs to be called. This approach can also be reflected in tail recursive construction. For example, the following is the traditional recursive definition of factorial method:
public static int FactorialRecursively(int n)
{
if (n == 0) return 1;
return FactorialRecursively(n - 1) * n;
}
Obviously, this is not a tail recursion method, of course we easily convert it to the previously mentioned tail recursion call method. However, we now "understand" it like this: every time we calculate the factorial of n, we actually "first get the factorial of n - 1" and then "multiple it with n and return", so our FactorialRecursively method can be modified to:
public static int FactorialRecursively(int n)
{
return FactorialContinuation(n - 1, r => n * r);
}
// 6. FactorialContinuation(n, x => x)
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
...
}
The meaning of the FactorialContinuation method is "calculate the factorial of n, pass the result into the continuation method, and return its call result". Therefore, it is easy to conclude that the FactorialContinuation method itself is a recursive call:
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
return FactorialContinuation(n - 1,
r => continuation(n * r));
}
The implementation of the FactorialContinuation method can be expressed as follows: "Computing the factorial of n, passing the result into the continuation method and returning it", that is, "calculating the factorial of n - 1, multiplying the result with n, and then calling the continuation method". In order to implement the logic of "and multiply the result with n, and then call the continuation method", the code constructs an anonymous method and passes it in the FactorialContinuation method again. Of course, we also need to supplement the recursive export conditions for it:
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
if (n == 0) return continuation(1);
return FactorialContinuation(n - 1,
r => continuation(n * r));
}
Obviously, FactorialContinuation implements tail recursion. If you want to calculate the factorial of n, we need to call the FactorialContinuation method as follows, which means "calculate the factorial of 10 and return the result directly":
FactorialContinuation(10, x => x)
To deepen your impression, can you understand the following way of calculating the nth term value of the "Fibonna" sequence?
public static int FibonacciContinuation(int n, Func<int, int> continuation)
{
if (n < 2) return continuation(n);
return FibonacciContinuation(n - 1,
r1 => FibonacciContinuation(n - 2,
r2 => continuation(r1 + r2)));
}
In functional programming, this type of call method forms "Continuation Passing Style（CPS）”. Since the Lambda expression in C# can easily form an anonymous method, we can also implement this method of calling in C#. You may wonder - Han, why do you have to be so complicated? Can't calculating factorials and "Fibonna" sequence be converted into tail recursive form in one go? But, how about you try the following example?
Pre-order traversal on the binary tree is a typical recursive operation, assuming that there is the following TreeNode class:
public class TreeNode
{
public TreeNode(int value, TreeNode left, TreeNode right)
{
= value;
= left;
= right;
}
public int Value { get; private set; }
public TreeNode Left { get; private set; }
public TreeNode Right { get; private set; }
}
So let's go through the traditional precedent:
public static void PreOrderTraversal(TreeNode root)
{
if (root == null) return;
();
PreOrderTraversal();
PreOrderTraversal();
}
Can you convert it to a tail recursive call in a "normal" way? PreOrderTraversal was called twice here, which means that there must be one call that cannot be placed at the end. At this time, we have to use Continuation:
public static void PreOrderTraversal(TreeNode root, Action<TreeNode> continuation)
{
if (root == null)
{
continuation(null);
return;
}
();
PreOrderTraversal(,
left => PreOrderTraversal(,
right => continuation(right)));
}
We now wrap each recursive call as the last operation of the code, and wrap the next operation with Continuation, so that tail recursion is achieved and stacking of stacking of stacking data. It can be seen that although using Continuation is a slightly "strange" way of using it, it is also an indispensable usage technique at some point.
Continuation improvements
Take a look at the preorder traversal implementation just now. Have you found a bit strange?
PreOrderTraversal(,
left => PreOrderTraversal(,
right => continuation(right)));
Regarding the last step, we construct an anonymous function as the Continuation of the second PreOrderTraversal call, but it directly calls the continuation parameter inside - so why don't we just hand it over to the second call? as follows:
PreOrderTraversal(,
left => PreOrderTraversal(, continuation));
We use Continuation to implement tail recursion, which actually throws the information that should have been allocated on the stack onto the managed heap. Each anonymous method is actually an object on the managed heap. Although such objects with a short survival cycle will not cause much problem with memory resources, it is definitely helpful to performance to minimize such objects. Here is another more obvious example, find the size of the binary tree:
public static int GetSize(TreeNode root, Func<int, int> continuation)
{
if (root == null) return continuation(0);
return GetSize(,
leftSize => GetSize(,
rightSize => continuation(leftSize + rightSize + 1)));
}
The GetSize method uses Continuation, and its understanding method is "get the size of the root, pass the result into continuation, and return its call result". We can rewrite it to reduce the number of times the Continuation method is constructed:
public static int GetSize2(TreeNode root, int acc, Func<int, int> continuation)
{
if (root == null) return continuation(acc);
return GetSize2(, acc,
accLeftSize => GetSize2(, accLeftSize + 1, continuation));
}
The GetSize2 method has an additional accumulator parameter, and its understanding method has also changed: "Accumulate the size of root on acc, pass the result into continuation, and return its call result". In other words, what GetSize2 returns is actually an accumulated value, not the actual size of the root parameter. Of course, when we call GetSize2, we just need to zero the accumulator:
GetSize2(root, 0, x => x)
Don't you know?
Finish
In imperative programming, we solve some problems that we can often use loops instead of recursion, so that we do not cause stack overflow due to data scale. However, in functional programming, the only way to implement "loop" is "recursion", so tail recursion and CPS are of great significance to functional programming. Understanding tail recursion is also of great help to programming thinking, so you might as well think and practice more so that this method can be used for your own use.