如何区分尾递归 calls/non-tail 递归调用？

Question

int gcd(int a,int b){
    if(a == b) return a;
    else if (a>b) return gcd(a-b,b);
    else return gcd(a,b);
    }

例如，我认为这是尾递归，因为你不调用另一个函数。

int gcd(int a,int b){
int x;
    if(a == b) x=a;
    else if (a>b) x= gcd(a-b,b);
    else x= gcd(a,b);
    return x;
    }

而且这是非尾递归，因为它调用了函数 gcd。

我说的对吗？或者有没有更简单的方法来区分tail/non-tail递归调用？

Answer 1

首先，出于 g++ TCO（tail-call 优化）的目的，无论您是进行递归调用还是完全调用不同的函数都没有关系 - 函数调用将被无条件跳转替换.

其次，当调用其他函数和 return 之间没有发生任何事情时，就会发生尾调用。它可以是 return 之前的最后一行，而不是 return 或 return 本身之前的最后一行。

例如，

} else {
   x = gcd(a,b);
   return x;
}

是一个 tail-call，因为 x 的值是 return 未修改的（没有任何反应）。

另一方面，

} else {
   x = gcd(a,b);
   return x + 1;
}

这不符合 TCO 的条件，因为 return 值已修改 - 正在发生。

但乐趣才刚刚开始！让我们谈谈 C++ 和析构函数。考虑以下代码：

int do2();

int do() {
    std::string x;
    // ...
    return do2();
}

是tail-call吗？第一印象 - 是的，是的。什么都没有发生，对吧？第二印象——不，不是！ x 析构函数需要发生！第三印象 - 是的 - 因为编译器看到 x 在调用之后没有被使用，所以可以很容易地在调用之前破坏 x。

但是，看看那个：

int do2(const std::string& );

int do() {
    std::string x;
    // ...
    return do2(x);
}

这里不是tail-call！ x 必须比 do2 长寿，所以回到我原来的（故意模糊的）定义，一些事情 正在发生。

Tail-calls很有趣！

How can I distinguish tail recursive calls/non-tail recursive calls?