抢先递归算法是否也是递归的？

根据定义：

非先决递归 ：如果一个函数根据其一个参数调用自己，那么这样的递归称为非先行递归（Non-Premptive Recursion）。 示例：阿克曼函数是非抢先递归的一个例子

private static int Foo(int i)
{
    if (i == 1000000)
        return i;

    if (i % 100 == 0)
    Console.WriteLine(i);

    return Foo(Foo(i+1));//last statement of the function
}

这里对Foo的递归调用是函数的最后一个语句，并不是表达式的一部分，它使它成为尾递归调用。 但另一方面，由于Foo函数已被称为参数，所以它将导致创建调用堆栈帧，在达到终止条件之前这些帧不能被丢弃。

在尾递归中，编译器可以优化尾递归调用，因为它不需要维护调用栈帧。 所以我的问题是 - 我的递归调用上面的代码段中的Foo真的是一个尾递归调用？

---

非抢先递归算法是否也可以递归？

是。

我在上面的代码片段中对Foo递归调用真的是一个尾递归调用吗？

哪一个？ 有两个递归调用：

…(Foo(i+1))… - 不是尾递归

return Foo(…); - 尾递归

外部的尾递归可以被优化：

private static int Foo(int i) {
    while (i != 1000000) {
        if (i % 100 == 0) Console.WriteLine(i);
        i = Foo(i+1);
    }
    return i;
}

编译器可能会推断Foo始终返回1000000 （如果它返回），因此会将该方法进一步重写为另一个尾递归，但这需要高级推理，而不是简单的转换：

private static int Foo(int i) {
    if (i != 1000000) {
        if (i % 100 == 0) Console.WriteLine(i);
    } else {
        return i;
    }
    return Foo(i+1);
}

然后可以通过尾递归规则将其转换为

private static int Foo(int i) {
    while (i != 1000000) {
        if (i % 100 == 0) Console.WriteLine(i);
        i = i+1;
    }
    return i;
}

链接地址: http://www.djcxy.com/p/80695.html

上一篇: preemptive recursive algorithm be tail recursive as well?

下一篇: Tail recursion in R