C++中的Tail Recursion,带有多个递归函数调用

Question

我正在阅读关于尾递归的这篇文章.

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

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

目前看,尾递归不适用.但是如果你看一下你所链接问题的第二个答案的结尾,你就可以看到如何恰当地重写这个功能.从...开始

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.