C语言函数递归

文章目录一、递归1. 递归的概念2. 递归的思想3. 递归的限制条件二、递归的一些经典例子1. 求一个数的阶乘2. 顺序打印一个整数的每一位3. 汉诺塔4. 青蛙跳台阶5. 斐波那契数列▲递归和迭代的对比一、递归1. 递归的概念递归是学习C语言函数绕不开的一个话题那什么是递归呢? 递归其实是一种解决问题的方法。在C语言中递归就是函数自己调用自己。2. 递归的思想递归就是把一个大型复杂的问题层层转化为一个与原问题相似的但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了。所以递归的思想就是把大事化小的过程。递归中的递就是递推归就是回归。3. 递归的限制条件递归在书写的时候有2个必要条件:●递归存在限制条件当满足这个限制条件时递归便不再继续。●每次递归调用之后会越来越接近这个限制条件。二、递归的一些经典例子1. 求一个数的阶乘#includestdio.hintfac(intn){if(n1||n0)return1;elsereturnn*fac(n-1);}intmain(){intn0;scanf(%d,n);intretfac(n);printf(%d的阶乘是%d\n,n,ret);return0;}运行结果上面通过函数递归来求一个正整数的阶乘那具体要怎么理解上面的代码呢分析一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积即n的阶乘公式为 nn*(n-1)! 并且0的阶乘为1。自然数n的阶乘写作n!。例如5! 5*4*3*2*14! 4*3*2*1所以 5! 5*4!这样的思路就是把一个较大的问题转换为一个与原问题相似但规模较小的问题来求解的。当n1或者n0的时候n的阶乘是1其余n的阶乘都是可以通过公式计算。那我们就可以写出函数fac求n的阶乘假设fac(n)就是求n的阶乘那么fac(n-1)就是求n-1的阶乘。所以构造的函数就是上面的fac。就是因为递归存在限制条件这就使得函数自己调用自己时会有结束的时候。当一个复杂的问题被拆解到不能再拆解的子问题时我们一眼就能看出子问题的答案。而求解出子问题的答案后我们就能逐一求解上一层的子问题以至于就能求解出原问题的答案了。2. 顺序打印一个整数的每一位输入一个整数n按照顺序打印整数的每一位。比如1.输入: 1234输出1 2 3 42.输入: 520输出5 2 0#includestdio.hvoidPrint(intn){if(n9)Print(n/10);printf(%d ,n%10);}intmain(){intn0;printf(请输入一个整数);scanf(%d,n);Print(n);return0;}运行结果这里需要知道一个知识点在C语言中整数除以一个整数得到的还是整数因为小数部分被丢弃掉了。①在C语言中一个整数除以10以后这个整数的个位会被丢掉得到个位前面的整数部分。比如327/10得到结果是32去掉了个位上的7。一个整数除以10以后位数会减少一位。②一个整数模(%)上10以后得到的是个位上的数字比如43%10得到的结果为3即余数就为3。那怎么理解上面的代码呢对于这个函数如果传进去的实参为1234进入函数就先判断n是否大于9如果n大于9就将n/10传给Print函数这里就又调用了Print函数直到n的值小于等于9以后if语句不成立了就执行printf(%d , n%10)这条语句即先打印1234的最高位1然后返回上一层继续打印百位的2然后再返回上一层打印十位上的3最后返回第一层打印个位上的4。图解释3. 汉诺塔先学习一下什么是汉诺塔(河内塔)? 汉诺塔是一个起源于印度古老传说的益智游戏由法国数学家爱德华·卢卡斯于1883年发明。汉诺塔的玩法对于上面的三个木桩中间的木桩上叠放有圆盘而且是按照小圆盘在大圆盘上方的次序叠放的。玩法是将一个木桩上的圆盘移动到另一个木桩上。移动规则●1.一次只能移动一个圆盘●2.每个木桩上只有最顶层的圆盘可以移动并且所移动的圆盘只能移动到空木桩上或者是它要比木桩顶层已存在的圆盘小。也就是说你每移动一次圆盘不管在哪根木桩上都要保证小圆盘在大圆盘的上方。我们从最简单的情况开始逐一讲解Ⅰ.如果木桩上只有一个圆盘的时候要把A柱上的圆盘移动到C柱上直接拿过去就好了。A→CⅡ.如果A木桩上有两个圆盘现在要把A木桩上的圆盘移动到C木桩上就需要借助B桩移动三次圆盘。共需三步A→BA→CB→CⅢ.如果A木桩上有三个圆盘现在要把A木桩上的圆盘移动到C木桩上最少需要移动多少次圆盘呢答案是最少需要7步A→CA→BC→BA→CB→AB→CA→C到第四步完以后发现最大的那个圆盘已经放在C柱上了剩下的两个圆盘要放到C柱上其实就跟上面只有两个圆盘的情况是一样的了只是这里需要借助A木桩移动到C木桩上位置不一样但是移动的次数和两个圆盘的情况是一样的。上面的4步加上只有两个圆盘情况下的3步最少只需要7步就能把A柱上的圆盘移动到C柱上。其实通过上面的1~3层圆盘的汉诺塔移动情况的分析不难发现这里就有递归的思想。像只有两个圆盘的情况我们要把A柱上最大的那个圆盘先移动到C柱上就要先把A柱上较小的圆盘先转移到B柱上然后才能把较大的那个圆盘移动到C柱上。然后你会发现剩下较小的圆盘要移动到C柱上就跟柱子上只有一个圆盘的情况是一样的只需要移动一步即可。同理A柱上如果有三个圆盘当把最大的那个圆盘移动到了C柱上后剩下的两个较小圆盘要移动到C柱上移动的次数就跟柱子上只有两个圆盘的情况是一样的只是借助的柱子不一样而已。那代码要怎么实现呢#includestdio.h//1.构造一个用来打印移动轨迹的函数voidPrint_Movetrack(charori,chardes){staticinttime0;//定义一个静态变量用来记录移动的次数printf(第%d步:%c-→%c\n,time,ori,des);}//2.汉诺塔代码的递归逻辑voidHanoi(intn,chara,charb,charc){if(n1){Print_Movetrack(a,c);}else{Hanoi(n-1,a,c,b);//Ⅰ将A柱上最大圆盘上方的n-1个圆盘借助C柱移动到B柱上Print_Movetrack(a,c);//Ⅱ将最大的圆盘从A柱移动到C柱上Hanoi(n-1,b,a,c);//Ⅲ将刚才移动到B柱上的圆盘借助A柱移动到C柱上}}intmain(){intn0;printf(请输入圆盘个数);scanf(%d,n);Hanoi(n,A,B,C);//n是圆盘个数A,B,C是三根木桩的编号return0;}运行结果最难理解的是这个函数是怎么构造出来的递归的逻辑是什么但是也紧扣递归的限制条件函数里面有使这个递归结束的限制条件每一次递归都会越来越接近这个限制条件。我们以A柱上有3个圆盘的情况来说明上面代码的递归逻辑函数在逐层调用自己时当满足限制条件后会逐一返回上一层继续执行上一层后续的代码。4. 青蛙跳台阶青蛙跳台阶问题一只青蛙去跳台阶它一次可以跳1个台阶一次也可以跳2个台阶。问如果现在有n层台阶青蛙要跳上这n层台阶共有多少种跳法分析Ⅰ.当只有一层台阶(n1)的时候青蛙只能跳1个台阶只能跳一次。如图所示Ⅱ.当有两层台阶(n2)的时候青蛙要跳上这两层台阶共有2种跳法。一是每次跳1个台阶共两次跳完二是一次跳2个台阶一次就跳完。如下图Ⅲ.当有三层台阶(n3)的时候要怎么算有多少种跳法呢首先分析一下青蛙一开始一次要么跳1个台阶要么跳2个台阶。①如果青蛙一开始一次跳了1个台阶那么就还剩下两层台阶那这两层台阶的跳法就跟上面只有两层台阶(n2)的跳法是一样的共有2种。②如果青蛙一开始一次跳了2个台阶那么就还剩下一层台阶这一层台阶的跳法就跟只有一层台阶(n1)的跳法一样只有一种。所以综上所述三层台阶的跳法总共有3种。就等于1层台阶和2层台阶的跳法之和。如下图所示Ⅳ.当有四层台阶(n4)的时候也是看青蛙一开始是怎么跳的如果一开始青蛙跳了1个台阶那后面就还剩三层台阶就跟上面只有三层台阶(n3)的跳法是一样的有3种跳法。如果一开始青蛙跳了2个台阶就还剩下两层台阶跟上面只有两层台阶(n2)的跳法一样有2种跳法。所以对于四层台阶总共有5种跳法。就等于2层台阶和3层台阶的跳法之和。Ⅴ.依次类推如果青蛙要跳上n层台阶这n层台阶的跳法就等于(n-2)层台阶和(n-1)层台阶的跳法之和。规律就是C语言代码的实现#includestdio.hintStep(intn){if(n1)return1;elseif(n2)return2;elsereturnStep(n-2)Step(n-1);}intmain(){intstep_num0;printf(请输入台阶层数);scanf(%d,step_num);printf(%d层台阶共有%d种跳法\n,step_num,Step(step_num));}运行结果我们把逐层台阶的跳法数量整理出来看通过上面的表也可以直观的看出来青蛙跳台阶的方法有多少种即第n层台阶跳法就等于n-2层台阶和n-1层台阶的跳法总和。5. 斐波那契数列先介绍一下斐波那契数列斐波那契数列又称黄金分割数列是由意大利数学家莱昂纳多·斐波那契以兔子繁殖为例而引入的故称为兔子数列。这个问题是兔子在出生两个月以后就有繁殖能力了成熟以后的一对兔子每个月都能生出一对小兔子如果所有的兔子都不死问在一年以后可以繁殖多少对兔子我们拿一对刚刚出生的兔子来分析①刚出生的一对小兔子第一个月还没有繁殖能力所以第一个月是一对兔子。②两个月以后生下一对小兔子所以现在共有两对小兔子。③第三个月后老兔子又生下一对兔子上个月新生的那一对兔子还没有繁殖能力所以现在一共有3对兔子。④第四个月后老兔子继续生下一对小兔子刚刚成熟的一对兔子也生下一对小兔子加上老兔子上个月刚出生的一对兔子现在一共就有5对兔子。…画出过程图来说明上图经过月份那里有一个0你可以理解为兔子刚出生的时刻。注意图中写的是经过的月份不是实际月份不要理解错误。所以通过上图可以直观的看出兔子繁殖对数的规律由表可以看出从第三月起每个月的兔子对数是前两个月的兔子对数之和。由此给出斐波那契数列的定义一个数列从第三项起每一项都等于前两项之和即1 1 2 3 5 8 13 21…这样一个数列。那递归的逻辑在这里就可以理解了那求第n个斐波那契数的代码实现#includestdio.h//斐波那契数的递归逻辑intFib(intn){if(n1||n2)return1;elsereturnFib(n-2)Fib(n-1);}intmain(){intn0;//这个n表示的是斐波那契数列中的第几项scanf(%d,n);printf(第%d项斐波那契数为%d\n,n,Fib(n));return0;}运行结果所以在第12个月的时候(还没有经过十二月)总共有144对兔子即288只兔子。如果是一年以后那就要经过十二月到下一年的一月开头那就有233对兔子即有466只兔子。▲递归和迭代的对比▲上面的青蛙跳台阶和斐波那契数列是非常相似的但是对于斐波那契数列来说不适合用递归的方法来实现。当我们要求的斐波那契数列的项数很大时比如我们要求第50项斐波那契数时这个递归所花费的时间是非常长的为什么呢看下面的递归逻辑图从上图可以看出递归程序会不断的展开在展开的过程中我们很容易就能发现在递归的过程中会有重复计算而且递归层次越深冗余计算就会越多。如果采用非递归的方式(迭代)效率就可以大大提高#includestdio.hintFib(intn){inta1;intb1;intc1;while(n2){cab;ab;bc;n--;}returnc;}intmain(){intn0;while(scanf(%d,n)!EOF){intretFib(n);printf(第%d项斐波那契数为%d\n,n,ret);}return0;}运行结果上面的这种求第几项斐波那契数的方法就是迭代法。每一次对过程的重复称为一次迭代而每一次迭代得到的结果将会作为下一次迭代的初始值。这种就叫做迭代法也称为辗转法。所以不是所有的问题都适合用递归的方法。Ⅰ.递归的优缺点优点●可以将大问题转化为小问题减少代码量。●可以去掉不断重复的代码使代码精简提升可读性。缺点●递归调用浪费空间递归太深还容易造成堆栈溢出问题。Ⅱ.迭代的优缺点优点●可以将重复的问题转化为一单问题的重复操作减少代码量。●代码运行效率高时间只因为循环次数的增加而增加没有额外的内存空间开销。缺点●代码不如递归简洁有时可能不容易理解。