0.前言:
递归的方法和思想可以解决很多繁琐的问题,并且在数据结构和算法的学习中有着举足轻重的地位,希望通过我的学习记录的总结能够帮到你更好地理解递归!
1. 递归是什么?
递归中的递就是递推,归就是回归。在C语⾔中,递归就是函数⾃⼰调⽤自己!
举个例子!一个初学者也能看懂的代码:
在这样一个简单的程序中,我们可以看到在一个main( )函数中,竟然又第二次调用了一个main( )函数,实际的运行历程如下,进入第一个main( )函数后,又立刻调用了第二个main( )函数,于是又返回到了第一个main( )函数,然后再次调用第二个main( )函数......反复进行,直到栈区爆满,又称:栈溢出(Stack overflow),程序崩溃!
1.1 递归的思想:
把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较⼩的⼦问题来求解;直到⼦问题不能再 被拆分,递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。
1.2 递归的限制条件(两个条件极为重要,是递归进行的前提条件!!!)
• (1)存在限制:递归存在限制条件,当满⾜这个限制条件的时候,递归便不再继续。
• (2)接近极限:每次递归调⽤之后越来越接近这个限制条件。
2.递归举例
2.1例一:求n的阶乘
关于阶乘是什么,不必多说,所以直接上一个普通版本的代码,也就是我们最熟悉的循环方法,又称迭代方法:
这个方法思路很简单,就是用循环的方法,计算一个值从1乘到n为止,再返回结果ret。
• • • 接下来分析一下递归方法及思路:
首先我们可以用分段函数的思想来对阶乘这个问题进行具体化:
从这个分段的函数式子中,可以清晰的看到n为0时的阶乘为1,n大于0时的阶乘,即为n*(n-1的阶乘),从这点我们就可以得出要进行递归的两个重要前提条件了!
(1)限制条件,只有n>0时才继续进行递归。
(2)接近极限,每次递归调用后,n都会-1,也就是向0接近了,越来越接近这个递归的极限,最后n减为0,也就停止进一步的递归了。
有了以上递归的两个重要条件后,我们就可以实际进行写程序了!
接下来以图例来表现递归的过程:
以4的阶乘为例,先看图,图后有详细的文字叙述过程,超细的哦!
首先n为4时进入Fact(4),n>0,进行4*Fact(3);
进入Fact(3),n>0,进行3*Fact(2);
进入Fact(2),n>0,进行2*Fact(1);
进入Fact(1),n>0,进行1*Fact(0);
进入Fact(0),n=0!递归到此结束,开始向上一级递归进行返回,向上一级递归Fact(1)的Fact(0)返回1;
于是Fact(1)=1*1,向上一级递归Fact(2)的Fact(1)返回1;
于是Fact(2)=2*1,向上一级递归Fact(3)的Fact(2)返回2;
于是Fact(3)=3*2,向上一级递归Fact(4)的Fact(3)返回6;
于是Fact(4)=4*6=24,到此返回结束,程序结束,得出结果。
下面是n=5时的直观图:
相信看完第一个递归的例子,你一定已经有些门道了吧!那我们继续下一个例子吧!
2.2 例二:求斐波那契数列的第n项的值
如果对斐波那契数列还不了解,可以先去看一下再回来!那我们直接上一个我们最熟悉的循环方法,也就是迭代方法,上代码!
这里就是一个while循环,先改变c的值,然后把b的值给第一项a,把第c的值给b,然后再改变c的值......依此类推,得到第n个数。
• • • 接下来看一下递归的方法及其思路!
思路依然是先将问题用分段函数具体化,找出两个重要前提条件,在进行写程序!
(1)限制条件,只有n>2时才继续进行递归。
(2)接近极限,每次递归调用后,n都会-1,也就是向2接近了,越来越接近这个递归的极限,最后n减为2,也就停止进一步的递归了。
既然已经找到了递归的两个前提条件,那我们直接看代码:
但是在这里就可以看出递归的弊端了!如下图:
可以看出要求出第50项的斐波那契数列,竟然需要如此之多次数的函数调用!直接栈溢出了!但是使用循环也就是迭代方法就可以避免这个问题,也就是说迭代方法比递归方法效率更高,但是递归方法要比迭代方法更简洁,更具思维量,各有利弊!
• • •所以接下来引出的尾递归可以避免这个问题:
• • •尾递归!!!!!
(1.)什么是尾递归?
尾递归是指一个函数在调用自身之后不再执行任何其他操作,而是将返回值直接传递给函数调用的上级,从而避免了新的调用栈帧的创建。换句话说,尾递归是指递归调用发生在函数的最后一个语句中,从而使得函数调用不需要保存多个调用栈帧,而只需一个即可。
(2.)尾递归与常规递归的区别
尾递归在递归过程中最后一步执行递归函数的步骤,并且在函数结束前不再需要执行任何其他计算或操作;而常规递归则在递归嵌套过程中创建多个栈帧以保存函数调用的相关信息。
(3.)尾递归的两大特点
- 在尾部调用的是函数自身 (Self-called);
- 可通过优化,使得计算仅占用常量栈空间 (Stack Space)。
(4.)尾递归实现斐波那契数列
相信看到这里,你一定已经对尾递归有一定的了解了!
2.3例三:顺序打印整数的每一位
即要求输⼊:1234 输出:1 2 3 4
简单分析一下:
首先如何得到每一位数字?
如何把大单元化为小单元?
这里就不再向前两个例子那么详细地解释了,咱们直接看代码!
很简洁,很简单,对不对!看分析!
3.总结:看完以上内容,相信你已经对于函数递归有了更深的理解。总的来说,递归在我们学习编程的过程中,总是时不时就会跳出来攻击我们,比如后续学习的数据结构中的二叉树等各种树,都需要扎实的递归知识作为基础,要想将递归运用的得心应手,就需要主动去寻找递归的两大前提条件,去写程序,去跑程序,去分析程序运行的全过程!
(难以避免会有手误的地方,若发现文章错误,欢迎指正;若有相关疑问,欢迎提问!
祝学业进步!)