侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

编程技巧:递归

kaixindeken
2021-04-18 / 0 评论 / 0 点赞 / 63 阅读 / 1,270 字

递归算不上任何数据结构和算法,但确实是一种很重要的编程技巧,很多算法也会用到递归来实现,比如归并排序、快速排序、二分查找等。

递归,简单来讲就是在函数定义中调用函数自身,从我们之前学习数学解题经验来讲,就是将一个大的问题拆分成多个小问题,逐一击破后最后归并结果。我们判断一个问题是否可以通过递归来解决,主要看它是否满足以下三个条件:

  • 一个问题的解可以分解为几个子问题的解
  • 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
    存在递归终止条件
  • 递归一定要有终止条件,否则会导致函数被无限调用最终致使内存溢出。

通过以上分析,我们可以整理出递归代码的编写思路:写出递归公式,找到终止条件。有句话叫做「人理解迭代,神理解递归」,说的就是递归代码可读性不好,理论上看,递归代码都是可以转化成迭代实现的,但是递归代码更简洁,更显逼格,我们在通过递归实现代码的时候,切忌试图通过人脑去分解每个步骤,那样会把自己搞晕的,这种重复迭代的事情交给计算机去做,我们要做的就是抽象出规律,写递归公式,找终止条件,再把它们转化为递归代码,就完事了。

说了这么多,最后通过一个案例来帮助你去理解和实际运用。递归的应用案例很多,比如经典的汉诺塔、斐波那契数列等,我们以斐波那契数列来演示下递归代码的编写,斐波那契数列是这样一组数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …(你可以去网上搜一下了解下这个数列的现实由来),求第n个数列的值。

按照我们前面列出的递归问题解题思路,首先抽象出这组数列的一般规律,将其整理成递归公式,会得出如下结论(索引从0开始,即第零项):

F0 = 0
F1 = 1
...
F(n) = F(n-1) + F(n-2)

这样,我们同时有了终止条件和递归公式,接下来,就是将其转化为递归代码了:

#include <iostream>
using namespace std;
int Fibonaccisequence(int n)
{
	if(n == 1 || n == 2)
	{
		return 1;
	}
	else
	{
		return Fibonaccisequence(n-1) + Fibonaccisequence(n-2);
	}
}
int main()
{
	int n;	//n表示为第几个数值
	while(cin >> n)
	{
		int res = Fibonaccisequence(n);
		cout << res <<endl;
	}
	return 0;
}

通过递归,我们用非常简洁的代码就实现了复杂的斐波那契数列的求解,如果要用迭代来实现这个逻辑,不定要写多少代码呢。

编写递归代码时有两个注意事项,一个是警惕堆栈溢出,为此要设定好终止条件和合理的递归层数,另一个是防止重复计算,因此,递归公式要经过认证求证,不能凭感觉贸然下手编码,不然真的会失之毫厘,谬以千里。

0

评论区