c - 尾递归 [C]

Question

我书中的问题是“哪些递归调用（不是函数！）是尾递归的？”

unsigned f(unsigned x) 
{ 
    if(x==0) return 1; 
    else if(x==1) return f(x-1); 
    else return 3*x + f(x-1); 
}

在这个例子中，我猜第一个是尾递归的，但第二个不是。但是，在以下情况下会发生什么，我们printf()在递归调用之前和之后也有？

void f(unsigned x) 
{
    if(x==0) return;
    else if(x==1) { f(x-1); printf("1"); }
    else if(x==2) { printf("2"); f(x-1); }
    else f(x-3);
}

考虑到我目前对尾递归的了解，我的猜测是第一个不是，但第二个和第三个是？我错了吗，如果是这样，你能解释一下这是如何工作的吗？

score 2 · Accepted Answer

在您的第一个示例中，您是对的，只有第一个调用可能是尾递归的。

在第二个示例中，第一次调用printf()可能是尾调用，第二次和第三次调用f()可能是尾递归。

这取决于您的实现细节，虽然使用的 ABI 可能会给出提示（这就是为什么调用f()比尾调用更可能是尾递归的原因printf()），但证据显然很弱。
该标准对这些问题保持沉默。

1 回答 1