做网站的怎么赚钱,百度推广管理,东莞公司想建网站,建筑工程网上叫什么一、递归概念
递归其实是⼀种解决问题的⽅法#xff0c;在C语⾔中#xff0c;递归就是函数⾃⼰调⽤⾃⼰。下面举一个例子#xff1a; 上述就是⼀个简单的递归程序#xff0c;只不过上⾯的递归只是为了演⽰递归的基本形式#xff0c;不是为了解决问题#xff0c;代码最终…一、递归概念
递归其实是⼀种解决问题的⽅法在C语⾔中递归就是函数⾃⼰调⽤⾃⼰。下面举一个例子 上述就是⼀个简单的递归程序只不过上⾯的递归只是为了演⽰递归的基本形式不是为了解决问题代码最终也会陷⼊死递归导致栈溢出Stack overflow。 递归的思想把⼀个⼤型复杂问题层层转化为⼀个与原问题相似但规模较⼩的⼦问题来求解直到⼦问题不能再被拆分递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。递归中的递就是递推的意思归就是回归的意思。
二、递归的限制条件
递归在书写的时候有2个必要条件
• 递归存在限制条件当满⾜这个限制条件的时候递归便不再继续。
• 每次递归调⽤之后越来越接近这个限制条件。
三、递归举例
3.1求n的阶乘
计算n的阶乘不考虑溢出n的阶乘就是1~n的数字累积相乘。
3.1.1分析和代码实现
首先我们要知道n的阶乘的公式n n ∗ (n − 1)!
例如 这样的思路就是把⼀个较⼤的问题转换为⼀个与原问题相似但规模较⼩的问题来求解的。通过上图继续分析假设求4的阶乘 当n1时n的阶乘是1其余n的阶乘都是可以通过上述公式进行拆分计算。
因此n的阶乘的递归公式如下 那我们就可以写出函数Fact求n的阶乘假设Fact(n)就是求n的阶乘那么Fact(n-1)就是求n-1的阶乘函数如下 测试 3.1.2画图推演 3.2顺序打印一个整数的每一位
输⼊⼀个整数m按照顺序打印整数的每⼀位。例如 3.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的每⼀位如下表⽰ 直到被打印的数字变成⼀位数的时候就不需要再拆分递归结束。代码如下 测试 在这个解题的过程中我们就是使⽤了⼤事化⼩的思路以1234为例把Print(1234)打印1234每⼀位拆解为⾸先Print(123)打印123的每⼀位再打印得到4Print(123)打印123每⼀位拆解为⾸先Print(12)打印12的每⼀位再打印得到的3直到Print打印的是⼀位数直接打印就⾏。
3.2.2画图推演
以1234每⼀位的打印来推演⼀下。 四、递归和迭代
在C语⾔中每⼀次函数调⽤都要需要为本次函数调⽤在栈区申请⼀块内存空间来保存函数调⽤期间的各种局部变量的值这块空间被称为运⾏时堆栈或者函数栈帧。函数不返回函数对应的栈帧空间就⼀直占⽤所以如果函数调⽤中存在递归调⽤的话每⼀次递归函数调⽤都会开辟属于⾃⼰的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。所以如果采⽤函数递归的⽅式完成代码递归层次太深就会浪费太多的栈帧空间引起栈溢出stack overflow的问题。
所以如果不想使⽤递归就得想其他的办法通常就是迭代的⽅式通常就是循环的⽅式。
⽐如计算n的阶乘。 事实上我们看到的许多问题是以递归的形式进⾏解释的这只是因为它⽐⾮递归的形式更加清晰但是这些问题的迭代实现往往⽐递归实现效率更⾼。 当⼀个问题⾮常复杂难以使⽤迭代的⽅式实现时此时递归实现的简洁性便可以补偿它所带来的运⾏时开销。
例如求第n个斐波那契数
注斐波那契数列第一项和第二项都是1后面每一项等于前两项相加。
假设我们写了一个Fib函数求第n个斐波那契数列那么根据斐波那契数列的性质可以得到以下公式 看到这公式我们很容易就能写出递归形式的代码 测试 当我们n输⼊为50的时候需要很⻓时间才能算出结果这个计算所花费的时间是我们很难接受的这也说明递归的写法是⾮常低效的那是为什么呢其实递归程序会不断的展开在展开的过程中我们很容易就能发现在递归的过程中会有重复计算⽽且递归层次越深冗余计算就会越多。如图 我们可以写代码统计一下第三个斐波那契数被计算的次数。 这⾥我们看到了在计算第40个斐波那契数的时候使⽤递归⽅式第3个斐波那契数就被重复计算了39088169次这些计算是⾮常冗余的。所以斐波那契数的计算使⽤递归是⾮常不明智的我们就得想迭代的⽅式解决。我们知道斐波那契数的前2个数都1然后前2个数相加就是第3个数那么我们从前往后从⼩到⼤计算就⾏了。代码如下 解释我们可以把a看成是第一个斐波那契数b看成是第二个斐波那契数c是要求的第n个斐波那契数因为前两个斐波那契数没有必要求所以求第三个及之后的斐波那契数需要累加n-2次所以循环条件是n2且每次n--。令a bb c是为了每次进入循环时ab分别为第n个斐波那契数的前2项和前1项。
五、拓展问题
青蛙跳台阶
题目一只青蛙一次可以跳上1级台阶也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。如图所示 思路由题可知当n等于1时只有一种跳法当n等于2时有两种跳法。假设我们写一个climbStairs函数用来求青蛙跳上一个n级台阶有多少种跳法那么当n大于等于3时第一次跳有两种情况如果第一次跳了一步那么后面的台阶就有climbStairsn-1种方法如果第一次跳了两步那么后面的台阶就有climbStairsn-2种方法。由此我们可以得到公式 代码为 测试
