函数式c#和尾部递归

本文关键字：尾部 递归 函数 | 更新日期: 2023-09-27 18:02:20

我有以下代码:

public static IEnumerable<T> cons<T>(T y, IEnumerable<T> xs)
{
    yield return y;
    foreach (var x in xs) yield return x;
}
public static bool empty<T>(IEnumerable<T> xs)
{
    return !xs.GetEnumerator().MoveNext();
}
public static T head<T>(IEnumerable<T> xs)
{
    Debug.Assert(!empty(xs), "Prelude.head: empty list");
    var e = xs.GetEnumerator(); e.MoveNext();
    return e.Current;
}
// repeat x is an infinite list, with x the value of every element
public static IEnumerable<T> repeat<T>(T x)
{
    return cons(x, repeat(x));
}

为什么head(repeat(2))不工作，但如果我用:

替换repeat的实现
// repeat x is an infinite list, with x the value of every element
public static IEnumerable<T> repeat<T>(T x)
{
    for(;;) yield return x;
}

工作吗?

函数式c#和尾部递归

您的第一个实现不是尾部递归的。最后要执行的是cons()调用，但是为了执行它，它必须计算repeat(2)。要做到这一点，它必须(再次)计算repeat(2)。依此类推，直到堆栈溢出。

第二个实现创建了一个枚举器，每次被要求输入下一个元素时，它都会无限期地返回x。没有重入，所以没有堆栈溢出

从表面上看，您的第一个示例从未终止，因此它只是破坏了堆栈。第二个示例是作为状态机实现的，它可以避免堆栈溢出。

相关文章：