目录什么是递归递归的限制条件递归的举例递归与迭代1. 递归是什么递归是学习 C 语言函数绕不开的一个话题那么什么是递归呢递归其实是一种解决问题的方法在 C 语言中递归就是函数自己调用自己。写一个史上最简单的 C 语言递归代码#includestdio.hintmain(){printf(hehe\n);main();//main函数中又调用了main函数return0;}上述就是一个简单的递归程序只不过上面的递归只是为了演示递归的基本形式不是为了解决问题代码最终也会陷入死递归导致栈溢出Stack overflow。1.1 递归的思想把一个大型复杂问题层层转化为一个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了。所以递归的思考方式就是把大事化小的过程。递归中的递就是递推的意思归就是回归的意思接下来慢慢来体会。1.2 递归的限制条件递归在书写的时候有 2 个必要条件递归存在限制条件当满足这个限制条件的时候递归便不再继续。每次递归调用之后越来越接近这个限制条件。在下面的例子中我们逐步体会这 2 个限制条件。2. 递归举例2.1 举例 1求 n 的阶乘一个正整数的阶乘factorial是所有小于及等于该数的正整数的积并且 0 的阶乘为 1。自然数 n 的阶乘写作 n!。题目计算 n 的阶乘不考虑溢出n 的阶乘就是 1~n 的数字累积相乘。2.1.1 分析和代码实现我们知道 n 的阶乘的公式n! n * (n - 1)!举例 5! 5 * 4 * 3 * 2 * 1 4! 4 * 3 * 2 * 1 所以5! 5 * 4!这样的思路就是把一个较大的问题转换为一个与原问题相似但规模较小的问题来求解的。当n 0的时候n 的阶乘是 1其余的阶乘都是可以通过公式计算。n 的阶乘的递归公式如下那我们就可以写出函数Fact求 n 的阶乘假设Fact(n)就是求 n 的阶乘那么Fact(n-1)就是求 n-1 的阶乘函数如下intFact(intn){if(n0)return1;elsereturnn*Fact(n-1);}测试#includestdio.hintFact(intn){if(n0)return1;elsereturnn*Fact(n-1);}intmain(){intn0;scanf(%d,n);intretFact(n);printf(%d\n,ret);return0;}运行结果这里不考虑 n 太大的情况n 太大存在溢出2.1.2 画图推演2.2 举例 2顺序打印一个整数的每一位输入一个整数 m按照顺序打印这个整数的每一位。比如输入1234 输出1 2 3 4输入520 输出5 2 02.2.1 分析和代码实现这个题目放在我们面前首先想到的是怎么得到这个数的每一位呢如果 n 是一位数n 的每一位就是 n 自己。n 是超过 1 位数的话就得拆分每一位。1234 % 10就能得到 4然后1234 / 10得到 123这就相当于去掉了 4。然后继续对123 % 10就得到了 3再除 10 去掉 3以此类推。不断的% 10和/ 10操作直到 1234 的每一位都得到。但是这里有个问题就是得到的数字顺序是倒着的。但是我们有了灵感我们发现其实一个数字的最低位是最容易得到的通过% 10就能得到。那么我们假设想写一个函数Print来打印 n 的每一位如下表示Print(n) 如果 n 是 1234那么表示为 Print(1234) //打印1234的每一位其中 1234 中的 4 可以通过% 10得到那么Print(1234)就可以拆分为两步Print(1234/10)//打印123的每一位printf(1234%10)//打印4完成上述 2 步那就完成了 1234 每一位的打印。那么Print(123)又可以拆分为Print(123/10) printf(123%10)。以此类推下去就有Print(1234) Print(123) printf(4) Print(12) printf(3) Print(1) printf(2) printf(1)直到被打印的数字变成一位数的时候就不需要再拆分递归结束。那么代码完成也就比较清楚voidPrint(intn){if(n9){Print(n/10);}printf(%d ,n%10);}intmain(){intm0;scanf(%d,m);Print(m);return0;}2.2.2 画图推演输入和输出结果在这个解题的过程中我们就是使用了大事化小的思路。把Print(1234)打印 1234 每一位拆解为首先Print(123)打印 123 的每一位再打印得到的 4。把Print(123)打印 123 每一位拆解为首先Print(12)打印 12 的每一位再打印得到的 3。直到Print打印的是一位数直接打印就行。以 1234 每一位的打印来推演一下3. 递归与迭代递归是一种很好的编程技巧但是很多技巧一样也是可能被误用的就像举例 1 一样看到推导的公式很容易就被写成递归的形式intFact(intn){if(n0)return1;elsereturnn*Fact(n-1);}Fact函数是可以产生正确的结果但是在递归函数调用的过程中涉及一些运行时的开销。在 C 语言中每一次函数调用都需要为本次函数调用在栈区申请一块内存空间来保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。函数不返回函数对应的栈帧空间就一直占用所以如果函数调用中存在递归调用的话每一次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。所以如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出stack overflow的问题。所以如果不想使用递归就得想其他的办法通常就是迭代的方式通常就是循环的方式。比如计算 n 的阶乘也是可以产生 1~n 的数字累计乘在一起的。intFact(intn){inti0;intret1;for(i1;in;i){ret*i;}returnret;}上述代码能够完成任务并且效率比递归的方式更高。事实上我们看到的许多问题是以递归的形式进行解释的这只是因为它比非递归的形式更加清晰但是这些问题的迭代实现往往比递归实现效率更高。当一个问题非常复杂难以使用迭代的方式实现时此时递归实现的简洁性便可以补偿它所带来的运行时开销。举例 3求第 n 个斐波那契数我们也能举出更加极端的例子就像计算第 n 个斐波那契数是不适合使用递归求解的但是斐波那契数的问题通常是使用递归的形式描述的如下看到这个公式很容易诱导我们将代码写成递归的形式如下所示intFib(intn){if(n2)return1;elsereturnFib(n-1)Fib(n-2);}测试代码#includestdio.hintmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);return0;}当我们 n 输入为 50 的时候需要很长时间才能算出结果这个计算所花费的时间是我们很难接受的这也说明递归的写法是非常低效的那是为什么呢其实递归程序会不断地展开在展开的过程中我们很容易就能发现在递归的过程中会有重复计算而且递归层次越深冗余计算就会越多。我们可以做个测试#includestdio.hintcount0;intFib(intn){if(n3)count;//统计第3个斐波那契数被计算的次数if(n2)return1;elsereturnFib(n-1)Fib(n-2);}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);printf(\ncount %d\n,count);return0;}输出结果这里我们看到了在计算第 40 个斐波那契数的时候使用递归方式第 3 个斐波那契数就被重复计算了 39088169 次这些计算是非常冗余的。所以斐波那契数的计算使用递归是非常不明智的我们就得想迭代的方式解决。我们知道斐波那契数的前 2 个数都是 1然后前 2 个数相加就是第 3 个数那么我们从前往后从小到大计算就行了。这样就有下面的代码intFib(intn){inta1;intb1;intc1;while(n2){cab;ab;bc;n--;}returnc;}迭代的方式去实现这个代码效率就要高出很多了。有时候递归虽好但是也会引入一些问题所以我们一定不要迷恋递归适可而止就好。拓展学习青蛙跳台阶问题汉诺塔问题以上 2 个问题都可以使用递归很好的解决有兴趣可以研究。