【转】递归与优化：尾递归

落日映苍穹つ 2021-12-05 22:05 329阅读 0赞

了解尾递归之前，先了解一下尾调用。

> 在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下该调用位置为尾位置。（摘自维基百科）

以上的解释来自维基百科。介绍了什么叫尾调用。例如：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>function foo(data) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>a(data);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>b(data);</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

这里的a(data)和b(data)都是函数调用，但是b(data)是函数返回前的最后运行的东西，所以也是所谓的尾位置。例如：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>function foo1(data) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>a(data) + 1;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div> 
      <code>function foo2(data) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>var</code> 
      <code>ret = a(data);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>ret;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div> 
      <code>function foo3(data) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>var</code> 
      <code>ret = a(data);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>(ret === 0) ? 1 : ret;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

这种就不是尾调用，对于foo1,最后一个动作是+1操作，并非是直接函数调用；对于foo3,是经过计算返回的结果，也不是尾调用。，foo2也不是尾调用

尾调用很重要的特性就是它可以不在调用栈上面添加一个新的堆栈帧，而是更新它。

接下来说一下什么是尾递归：

> 若一个函数在尾位置调用本身（或是一个尾调用本身的其他函数等），则称这种情况为尾递归，是递归的一种特殊情形。而形式上只要是最后一个return语句返回的是一个完整函数，它就是尾递归。这里注意：尾调用不一定是递归调用，但是尾递归一定是尾调用。

接下来通过斐波那契数列和阶乘来进一步理解尾递归的含义。

**斐波那契数列**

常规的斐波那契数列算法可能是这样的：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>int</code> 
      <code>fib(</code> 
      <code>int</code> 
      <code>n) { </code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(n &lt;= 2) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>1;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>fib(n - 1) + fib(n - 2);</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

上面的这种递归计算最终的return操作是加法操作。所以不是尾递归。

如果用尾递归就是这样的：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>/**</code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>计算第n位斐波那契数列的值</code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>@param n 第n个数</code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>@param acc1 第n个数</code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>@param acc2 第n与第n+1个数的和</code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>@return 返回斐波那契数列值</code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>*/</code> 
     </div> 
     <div> 
      <code>int</code> 
      <code>tailfib(</code> 
      <code>int</code> 
      <code>n,</code> 
      <code>int</code> 
      <code>acc1,</code> 
      <code>int</code> 
      <code>acc2) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(n &lt; 2) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>acc1;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>tailfib(n-1,acc2,acc1 + acc2); </code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

比如我们想计算第10位斐波那契数列的值，只需要fib(10，1，1)即可。

看一下测试效果，测试程序如下：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>int</code> 
      <code>main(</code> 
      <code>int</code> 
      <code>argc, </code> 
      <code>const</code> 
      <code>char</code> 
      <code>* argv[]) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>clock_t start,finish;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>start = clock();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf(</code> 
      <code>"计算结果：%d\n"</code> 
      <code>, fib(45));</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>finish = clock();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf(</code> 
      <code>"花费时间--------%lu\n"</code> 
      <code>,finish - start);</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>start = clock();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf(</code> 
      <code>"计算结果：%d\n"</code> 
      <code>, tailfib(45,1,1));</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>finish = clock();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf(</code> 
      <code>"花费时间--------%lu\n"</code> 
      <code>,finish - start);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>0;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

计算结果如下：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>计算结果：1134903170</code> 
     </div> 
     <div> 
      <code>花费时间--------5540692</code> 
     </div> 
     <div> 
      <code>计算结果：1134903170</code> 
     </div> 
     <div> 
      <code>花费时间--------4</code> 
     </div> 
     <div> 
      <code>Program ended with exit code: 0</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

效率可想而知。

**阶乘**

常规的计算阶乘的方法可能是这样的：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>int</code> 
      <code>fac(</code> 
      <code>int</code> 
      <code>n) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(n == 1) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>1;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>fac(n-1) * n;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

复杂度为O(n)

尾递归的算法是这样的：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>int</code> 
      <code>tailfac(</code> 
      <code>int</code> 
      <code>n,</code> 
      <code>int</code> 
      <code>sum) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(n == 1) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>sum;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>fac(n-1, n * sum);</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

复杂度为O(1)

测试一下效率,测试程序如下：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>int</code> 
      <code>main(</code> 
      <code>int</code> 
      <code>argc, </code> 
      <code>const</code> 
      <code>char</code> 
      <code>* argv[]) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>clock_t start,finish;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>start = clock();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf(</code> 
      <code>"计算结果：%d\n"</code> 
      <code>, fac(16));</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>finish = clock();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf(</code> 
      <code>"花费时间--------%lu\n"</code> 
      <code>,finish - start);</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>start = clock();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf(</code> 
      <code>"计算结果：%d\n"</code> 
      <code>, tailfac(16,1));</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>finish = clock();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf(</code> 
      <code>"花费时间--------%lu\n"</code> 
      <code>,finish - start);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>0;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

测试结果：

尾递归效率比较高，但是个人觉得有尾递归算法理解起来会比较困难，你需要标注一下每个传入参数的作用，否则刚接触不一定会用这个算法。

参考资料：[阮一峰的网络日志][Link 1] [维基百科][Link 2]

转载请标注来源：[http://www.cnblogs.com/zhanggui/p/7722541.html][http_www.cnblogs.com_zhanggui_p_7722541.html]

转载于:https://www.cnblogs.com/schips/p/11013899.html

[Link 1]: http://www.ruanyifeng.com/blog/2015/04/tail-call.html
[Link 2]: https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8
[http_www.cnblogs.com_zhanggui_p_7722541.html]: http://www.cnblogs.com/zhanggui/p/7722541.html