gpt4 book ai didi

c++ - 使用尾递归实现 Tak 函数

转载 作者:行者123 更新时间:2023-11-28 07:17:44 25 4
gpt4 key购买 nike

是否可以实现 Tak function :

enter image description here

以某种方式在 C/C++ 中递归尾部以便 gcc/g++ 可以执行尾部递归优化?
我不确定嵌套的递归函数调用是否会使编译器感到困惑。

最佳答案

C++中的尾递归优化要求只有1次递归调用(基本上可以将其转换为循环)并且递归调用是函数中的最后一个操作:

例子:

unsigned int f( unsigned int a ) 
{
if ( a == 0 )
{
return a;
}
return f( a - 1 ); // tail recursion
}

由于 Tak 函数每次“迭代”需要 4 次递归调用:

int tak(int x, int y, int z)
{
if (x >= y)
{
return z;
}
else
{
return tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)); // this is why it cannot happen
}
}

如您所见,最后一个调用是递归的,但它内部有 3 个递归调用。这会阻止尾递归优化(并且没有将其转换为非递归循环的逻辑方法 - 这是获得尾递归优化所必需的)。

另一种实现方式是:

int tak(int x, int y, int z)
{
while (x > y)
{
int oldx = x, oldy = y;
x = tak(x - 1, y, z);
y = tak(y - 1, z, oldx);
if (x <= y)
break;
z = tak(z - 1, oldx, oldy);
}
return z;
}

这再次表明,即使在循环形式中,它仍然是递归的,从而防止了尾递归优化。

关于c++ - 使用尾递归实现 Tak 函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19962711/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com