c++ - 具有多个递归函数调用的 C++ 中的尾递归

Question

我正在读这个post关于尾递归。

我将复制发布的解决方案:

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

我想知道，如果结果取决于多个递归函数调用怎么办？例如:

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
       }
    return f(a -1) + f( a - 1 );   
}

上面的代码会被编译器优化吗？

Answer 1

就目前而言，尾递归不适用。但是如果你看看 second answer 的末尾在您链接到的问题上，您可以看到如何适本地重写函数。开始于

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
    }
    return f(a-1) + f(a-1);   
}

重写如下:

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
    }
    return 2 * f(a-1);  
}

即使是现在，尾递归仍然不能直接应用。我们需要确保返回严格采用 return f(....) 形式。再次重写函数:

unsigned int f( unsigned int a, unsigned int multiplicative_accumulator = 1 ) {
    if ( a == 0 ) {
          return multiplicative_accumulator * a;
    }
    return f(a-1, multiplicative_accumulator * 2 );   
}

现在，尾递归适用了。这使用 multiplicative_accumulator 的默认值(感谢@Pubby)，以便第一次调用 f 可以简单地是 f(x)，否则你将不得不写一些东西f(x,1)。

感谢@SteveJessop 的最后几点说明:

• 将 f(a+1)+f(a+1) 更改为 2*f(a+1) 是安全的，因为 f 没有副作用(打印、修改堆，诸如此类)。如果 f 确实有副作用，那么重写将无效。
• 原版相当于 (2*(2*(2*a))(或者更准确地说，(((a+a)+(a+a))+ ((a+a)+(a+a)))) 而当前版本更像是 (((2*2)*2)*a)。这很好，尤其是对于整数，因为乘法是关联和分配的。但这与 float 不完全等价，在那里你可能会得到小的舍入差异。使用浮点运算，有时 a* b*c 可能与 c*b*a 略有不同。