非抢占递归算法也可以是尾递归吗?

Question

根据定义:

非抢占式递归: 如果一个函数从它的一个形参调用它自己，那么这样的递归称为非抢占式递归。示例:Ackermann函数是一个非抢占式递归的例子

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在上面的代码片段真的是一个尾部递归调用?

Answer 1

非抢占递归算法也可以是尾递归吗?

是的。

在上面的代码片段中，我对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;
}