是否可以实现Tak 功能:
以某种方式在 C/C++ 中递归尾部,以便 gcc/g++ 可以执行尾递归优化?
我不确定嵌套的递归函数调用是否会混淆编译器。
是否可以实现Tak 功能:
以某种方式在 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;
}
这再次表明,即使是循环形式,它仍然是递归的,从而阻止了尾递归优化。
直接从您的数学定义出发,我们可以将函数编写为:
int tak(int x, int y, int z){
if(x>y)
return tak(tak(1-x,y,z), tak(y-1,z,x), tak(z-1,x,y));
else
return z;
}
但是,您不能使用尾递归来执行此操作,因为它无法转换为循环。因为有不止一个招聘电话。