C#中的尾递归与Continuation详解

前端技术 2023/09/05 C#

这几天恰好和朋友谈起了递归，忽然发现不少朋友对于“尾递归”的概念比较模糊，网上搜索一番也没有发现讲解地完整详细的资料，于是写了这么一篇文章，权当一次互联网资料的补充。:P

递归与尾递归

关于递归操作，相信大家都已经不陌生。简单地说，一个函数直接或间接地调用自身，是为直接或间接递归。例如，我们可以使用递归来计算一个单向链表的长度：

尾递归”。与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化1便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。

有些朋友可能已经想到了，尾递归的本质，其实是将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中。对于GetLengthTailRecursively方法，我们在调用时需要给出acc参数的初始值：

Continuation Passing Style（CPS）”。由于C#的Lambda表达式能够轻松构成一个匿名方法，我们也可以在C#中实现这样的调用方式。您可能会想——汗，何必搞得这么复杂，计算阶乘和“菲波纳锲”数列不是一下子就能转换成尾递归形式的吗？不过，您试试看以下的例子呢？

对二叉树进行先序遍历（pre-order traversal）是典型的递归操作，假设有如下TreeNode类：

复制代码 代码如下:

public class TreeNode
{
    public TreeNode(int value, TreeNode left, TreeNode right)
    {
        this.Value = value;
        this.Left = left;
        this.Right = right;
    }

    public int Value { get; private set; }

    public TreeNode Left { get; private set; }

    public TreeNode Right { get; private set; }
}

本文地址：https://www.stayed.cn/item/13254

转载请注明出处。

本站部分内容来源于网络,如侵犯到您的权益,请 联系我

我的博客

人生若只如初见，何事秋风悲画扇。

我的标签

随笔档案