C++递归使用

矫情吗；* 2024-03-16 22:54 83阅读 0赞

首先来谈谈常规的递归概念，**递归递归先递后归**。指的是我问你，你问他，他问下一个人这样层层递进直到得知结果并返回的过程。因此递归作为一种[算法][Link 1]在[程序设计语][Link 2]中广泛应用。 绕口一点来说递归就是一个过程或[函数][Link 3]在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的[语句][Link 4]来定义对象的[无限集合][Link 5]。**一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。最基本的递归结构如下：**

<table> 
 <tbody> 
  <tr> 
   <td></td> 
   <td><code>void countdown(int n)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>{ </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; "n is " &lt;&lt; n &lt;&lt; " addr: "&lt;&lt;&amp;n&lt;&lt; endl; </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (n) //边界条件：终止递归的条件</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>countdown(n-1);//前进段：递归终止条件不满足时</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; "n is " &lt;&lt; n &lt;&lt; " addr: " &lt;&lt; &amp;n &lt;&lt; endl; //返回段：递归终止条件满足时</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
 </tbody> 
</table>

为了更加深刻的理解递归的过程，我们给传递的变量n取地址并打印，运行结果如下：

![77f93ba6da12e628df465f25dbf110fc.png][]

根据程序运行的结果来看，递归实际就是压栈出栈的过程，何时压栈何时出栈取决于边界条件的制定，因此当递归缺少边界条件时程序与无限调用，直至当前程序栈全部耗尽，运行强制停止！

![ed2b6c5ce07bf5d3912a6ca7ea8e5c69.png][]

我们稍微复杂下，因为当一项工作不断分为两项比较小且类似的工作时，递归的递归的递归的......就是非常好用的一种算法。我们假设有这样一个问题**“将刻度尺切割对半并读取切割处的值，在平分刻度尺后在左端和右端继续切割并读值，依次类推”**，来看下面的这段代码：

<table> 
 <tbody> 
  <tr> 
   <td></td> 
   <td><code>void cut_ruler(double start,double end)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>{ </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>double middle_value = (start + end) / 2;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>double light_start, light_end;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>double right_start, right_end;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>light_start = start;//获取左端的起始值</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>light_end = middle_value;//获取左端的结束值</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>right_start = middle_value;//获取右端的起始值</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>right_end = end;//获取右端的结束值</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; "the light_start:" &lt;&lt; light_start &lt;&lt; endl;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; "the light_end:" &lt;&lt; light_end &lt;&lt; endl;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; "the right_start:" &lt;&lt; right_start &lt;&lt; endl;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; "the right_end:" &lt;&lt; right_end &lt;&lt; endl;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; "the middle:" &lt;&lt; middle_value &lt;&lt; endl;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; endl;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if ((end-start) &gt; 1)//终止条件</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>{ </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cut_ruler(light_start, light_end);//左边值，递归前进</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cut_ruler(right_start, right_end);//右边值，递归前进</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>cout &lt;&lt; "the middle return:" &lt;&lt; middle_value &lt;&lt; endl;//递归返回</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
 </tbody> 
</table>

我们来看运行结果：

![37bc8d2ad90cb0c455ceae00c15a6246.png][]

从程序结果可以看出，递归运行时，函数自身将不断调用两个函数自身，形似二叉树的延申过程，同上所述递归经常用于边界与过程都已知的重复计算，类如斐波那契数列，阶乘，网页的前进与返回，arxml，cdd数据库解析等；对了，需要注意一点的是C中main函数自身可以递归，但是C++中不行。好啦，本次递归的原理就说到这里，文中如有错误请各路大佬指点，感兴趣的可以阅读其他更加深入的大佬文章~

[Link 1]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95
[Link 2]: https://baike.baidu.com/item/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E8%AF%AD%E8%A8%80
[Link 3]: https://baike.baidu.com/item/%E5%87%BD%E6%95%B0
[Link 4]: https://baike.baidu.com/item/%E8%AF%AD%E5%8F%A5
[Link 5]: https://baike.baidu.com/item/%E6%97%A0%E9%99%90%E9%9B%86%E5%90%88
[77f93ba6da12e628df465f25dbf110fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/da6a039b12e54940bfb793f3a58c6d45.png
[ed2b6c5ce07bf5d3912a6ca7ea8e5c69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b933a8d26ca345b39cd8a9148a5863eb.png
[37bc8d2ad90cb0c455ceae00c15a6246.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/191c7b1cb8e04aa8bcc29b765135ff1f.png