c# - 函数式 C# 和尾递归

Question

我有以下代码:

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;
}

有用吗？

Answer 1

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

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