聊一下什么是递归
程序员文章站
2022-05-15 14:07:42
...
因为最近一些繁琐的事情,很久没有发博客了,其实这段时间我一直在想我要写些什么,思来想去,还是聊聊递归吧。
什么是递归?
这就是递龟,就聊到这吧。
开个玩笑。
递归,通俗的说,就是函数自己调用自己的方法。
用网友的一张图解释就是…
更标准一些,用数学函数解释就是嵌套函数自身,如f(f(f(f(f(x)))))。
构成递归需具备的条件
- 子问题须与原始问题为同样的事,且更为简单;
- 不能无限制地调用本身,须有个出口,化简为非递归状况处理。
对于条件2,若函数没有设置出口的话,则会发生我们常说的死循环,所以,我们必须设置一个出口,使其跳出。
递归的经典应用——斐波那契数列
利用递归,我们就可以解决某些经典的问题,如斐波那契数列,就是俗称的兔子问题,这里引用百度百科的解释
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……
观察数列可得,除了第一项和第二项,所有的数列的值都是前一项和前一项的前一项的加和,转换成函数也就是f(n) = f(n-1) + f(n-2),这就符合递归所具备的条件1了
引用网络上的流程图,如下
由这张流程图我们清晰的知道,实现斐波那契数列时总在不停的要用到F1与F2,而且第n项(n>2)的值总等于第n-1项的值与n-2的值之和。
由此,利用递归,写出代码
long long Fibonacc(long long n)//斐波那契数列,返回斐波那契数列的第n项
{
if (n == 1 || n == 2)//设置出口
{
return 1;
}
else if(n == 0)//设置输入0的出口
{
return 0;
}
else if(n > 2)
{
return Fibonacc(n - 1) + Fibonacc(n - 2);//其实都是在不停调用n=1与n=2的情况,若统计n=1与n=2的调用次数,会发现调用次数会很大。
}
}
递归的其他简单应用
阶乘
利用递归,我们也可以实现数学的阶乘操作
long long powder_(long long num)//阶乘
{
if (num == 1)//出口
{
return num;
}
return num * powder_(num - 1);
}
利用静态变量在函数生存周期只声明一次的特点,我们也可以这样
long long powder(long long num)//阶乘
{
static long long m = 1;//声明一个初始值为1的静态变量,这里利用了静态变量在整个函数周期中只声明一次的原理,下同
if (num == 1)
{
return m;
}
m *= num;
powder(num - 1);
}
累加
long long sum_(long long begin,long long end)//累加
{
if (begin > end)
{
return 0;
}
return begin + sum_(begin + 1, end);
}
类似的,利用静态变量,也可以这样
long long sum(long long begin,long long end)//累加
{
static long long x;//声明静态变量,默认初值为0,这里利用了静态变量在整个函数周期中只声明一次的原理,同上
if (begin == end)
{
return x + end;
}
x += begin;
sum(begin+1, end);
}
同样的,利用递归也能实现累乘操作,这里就不再说了,感兴趣的小伙伴可以自己思考写出,关于递归,就聊到这吧。
结语
- 引用网络上的话,递归很像某些部门的踢皮球行为,“踢皮球”-常用来形容*职能部门职责不清,相互推诿,比如你要到部门A盖个章,A叫你先去部门B盖章,B叫你去部门C盖章…这种将工作以踢皮球的方式甩给其他人做的方式其实很适用于递归。
- 递归很明显的有点就是代码简洁且容易验证正确性,但是若递归函数中每次都需要创建新的变量的话,执行效率就会受到影响,与循环相比,递归的效率会低一些。
- 如果没有明显的相似性,需要主动构造
- 不能构造的原因可能时缺少参数
- 递归与数学上的递推有很大的相似性