<div class="._5ce-wx-style" style="font-size:16px;">
<div class="rich_media_content" id="js_content">
<p>递归</p>
<p>在学习递归之前，首先应该掌握的是<strong>函数</strong>的相关知识，如何定义以及调用函数。函数的作用在于</p>
<ul><li><p>代码重用</p></li><li><p>问题分解</p></li></ul>
<p>并且能够一定程度上体会模块化编程的思想。</p>
<p>递归实际上也是一种函数的应用。函数自己调用自己，这种调用称为“递归”。这种函数被称为“递归函数”。</p>
<p>观察以下程序，思考输出结果</p>
<pre class="blockcode"><code>#include void function (int n) {<!-- --> if (n > 0) {<!-- --> function(n-1); for(int i = 1; i <= n; i++) printf ("#"); printf("\n"); }}int main () {<!-- --> function(5); return 0;}</code></pre>
<p>以上明显存在自我调用，因此是递归函数，上面函数执行过程如下图</p>
<p><img alt="dff34597a95aab65807cab62719d7bb3.png" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-631468fe0ef04d52950cf2447b590cbd.png"></p>
<p>每一次函数的调用，都会被存入系统栈空间。函数终止条件为n<=0，当到达使得n==0的调用函数，才会停止继续调用自身，返回上一次调用也就是function(1)，接下来执行for循环语句，执行完该次调用，返回到function(2)，继续执行for循环，依次类推，执行到function(5)。</p>
<h2><span style="font-weight:bold;">递归思想</span></h2>
<p>根据之前的例子，可以发现一个问题想用递归函数来解决，需要满足两个条件：</p>
<p>1、可以将原问题转换为一个新问题，新问题的解法相同于原问题，只是问题的规模缩小</p>
<p>2、递归函数要明确一个终止条件，在到达终止条件的的时候递回。</p>
<p><strong>例1、阶乘的求法</strong></p>
<p>题目描述：</p>
<p>输入一个n，用递归的方式求出n的阶乘(1</p>
<p>(n! = n×(n-1)×(n-2)…2×1)</p>
<p>例如，输出 5，输出 120</p>
<p><strong>问题分析：</strong></p>
<p>n! = n × (n-1)!</p>
<p> 根据上面的分析结果来看，对于n的阶乘问题，我们可以转化为(n-1)的阶乘问题，同理(n-1)的阶乘可以转换为(n-2)的阶乘，这样问题的规模在不断缩小，直到1，结束递归。</p>
<p>而递归关系式可以被表示如下</p>
<p><img alt="9dfcdc5601a86b3936e2b933b1911c36.png" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-7918cbcb7343e4481e02ef1a8c47f045.png"></p>
<p>程序如下</p>
<pre class="blockcode"><code>#include int factorial (int n) {<!-- --> if (n == 1) return 1; return n * factorial(n-1);}int main () {<!-- --> int n; scanf ("%d", &n); printf("%d", factorial(n)); return 0;}</code></pre>
<p>用5的阶乘作为例子，上述递归代码执行过程可表示为下图，当n=1时，出现边界，开始返回</p>
<p><img alt="c0f9d7a3582c608f102259c03f50cf79.png" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-c90ef9a4a13561ba97b51183db6e80c2.png"></p>
<h2><span style="font-weight:bold;">题目练习</span></h2>
<h4><span style="font-weight:bold;">1.求斐波那契数列的第n项</span></h4>
<p>输入n,按照斐波那契数列，输出第n项的大小(0</p>
<p>参考程序</p>
<pre class="blockcode"><code>#include int fibonacci (int n) {<!-- --> if (n == 1) return 1; if (n == 2) return 1; return fibonacci(n-1) + fibonacci(n-2);}int main () {<!-- --> int n; scanf ("%d", &n); printf("%d", fibonacci(n)); return 0;}</code></pre>
<h4><span style="font-weight:bold;">2.数的倒序</span></h4>
<p>输入一个非负整数n(int范围内)，使用递归的方法输出这个数的倒序结果(保留前置0)。</p>
<p>参考程序</p>
<pre class="blockcode"><code>#include void reverse (int n) {<!-- --> if (n) {<!-- --> printf("%d", n%10); reverse(n/10); }}int main () {<!-- --> int n; scanf ("%d", &n); reverse(n); return 0;}</code></pre>
<h4><span style="font-weight:bold;">3.将10进制的数转化为8进制的数</span></h4>
<p>参考程序</p>
<pre class="blockcode"><code>#include void convert (int n, int r) {<!-- --> if (n == 0) return ; convert (n/r, r); printf("%d", n%r);}int main () {<!-- --> int n; scanf ("%d", &n); convert(n, 8); return 0;}</code></pre>
<h2><span style="font-weight:bold;">小结</span></h2>
<p>采用“递归”思路解决问题的方法都是递归算法。</p>
<p>算法适用场景：</p>
<ul><li><p>数据的<strong>定义形式</strong>上是递归的，例如阶乘</p></li><li><p>问题的解法是<strong>重复执行某种操作</strong>的，并且问题规模在缩小，有明显的边界。例如最大公约数、汉诺塔</p></li><li><p>数据之间的<strong>逻辑关系</strong>是递归的，例如树、图的定义和操作</p></li></ul>
|
|
转播
