欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

聊一下什么是递归

程序员文章站 2022-05-15 14:07:42
...

因为最近一些繁琐的事情,很久没有发博客了,其实这段时间我一直在想我要写些什么,思来想去,还是聊聊递归吧。

什么是递归?

聊一下什么是递归
这就是递龟,就聊到这吧。

开个玩笑。
递归,通俗的说,就是函数自己调用自己的方法。
用网友的一张图解释就是…
聊一下什么是递归
更标准一些,用数学函数解释就是嵌套函数自身,如f(f(f(f(f(x)))))。

构成递归需具备的条件

  1. 子问题须与原始问题为同样的事,且更为简单;
  2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

对于条件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);
}

同样的,利用递归也能实现累乘操作,这里就不再说了,感兴趣的小伙伴可以自己思考写出,关于递归,就聊到这吧。

结语

  1. 引用网络上的话,递归很像某些部门的踢皮球行为,“踢皮球”-常用来形容*职能部门职责不清,相互推诿,比如你要到部门A盖个章,A叫你先去部门B盖章,B叫你去部门C盖章…这种将工作以踢皮球的方式甩给其他人做的方式其实很适用于递归。
  2. 递归很明显的有点就是代码简洁且容易验证正确性,但是若递归函数中每次都需要创建新的变量的话,执行效率就会受到影响,与循环相比,递归的效率会低一些。
  3. 如果没有明显的相似性,需要主动构造
  4. 不能构造的原因可能时缺少参数
  5. 递归与数学上的递推有很大的相似性