猫史档案馆

今天我要讲的又是一个极其重要且实用的两个经典程序设计策略：递推和递归

递归是算法中一种非常重要的思想，应用也很广，小到阶乘,再在工作中用到的比如统计文件夹大小，大到 Google 的 PageRank 算法都能看到，也是面试官很喜欢的考点

最近看了不少递归的文章，收获不小，不过我发现大部分网上的讲递归的文章都不太全面，主要的问题在于解题后大部分都没有给出相应的时间/空间复杂度，而时间/空间复杂度是算法的重要考量!递归算法的时间复杂度普遍比较难（需要用到归纳法等），换句话说，如果能解决递归的算法复杂度，其他算法题题的时间复杂度也基本不在话下。另外，递归算法的时间复杂度不少是不能接受的，如果发现算出的时间复杂度过大，则需要转换思路，看下是否有更好的解法 ，这才是根本目的，不要为了递归而递归！

递归概念及定义：

简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。

以阶乘函数为例,如下, 在 factorial 函数中存在着 factorial(n - 1) 的调用，所以此函数是递归函数

C++；

#include <iostream>

using namespace std;

int f (int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	return  f(n - 1) + f(n - 2);
}

int main()
{
	
	int n;
	cin >> n;
	cout << f(n) << endl;
	
	return 0;
}

kitten；

进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即到达递归边界），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。

求解问题 f(6), 由于 f(6) = n * f(5), 所以 f(6) 需要拆解成 f(5) 子问题进行求解，同理 f(5) = n * f(4) ,也需要进一步拆分,... ,直到 f(1), 这是「递」，f(1) 解决了，由于 f(2) = 2 f(1) = 2 也解决了,.... f(n)到最后也解决了，这是「归」，所以递归的本质是能把问题拆分成具有相同解决思路的子问题，。。。直到最后被拆解的子问题再也不能拆分，解决了最小粒度可求解的子问题后，在「归」的过程中自然顺其自然地解决了最开始的问题。

图示；

递归函数有以下几个特点；

1.最先开始的递归最晚结束。

2.递归解决问题的数值增大，其时间复杂度成指数增长。

3.简化程序设计。

4.空间复杂度为S(n)级别。

接下来是递推；

递推概念及定义：

递推算法是通过利用递推式（即一个数列前面的项和后面的项的关系）来将一个庞大的计算过程分解为若干次重复的计算而后得出结果的这个过程叫做递推，而数列最前面开始的那几项就叫做递推边界。 什么问题可用递推解决？ 如果数列{a_n}的第n项与它前一项或几项的关系可以用一个式子来表示（递推式），那么这个问题就可以用递推很轻松的解决。 递推算法有以下几个特点； 1.时间复杂度相较递归低，为O(n)级别。 2.简化程序设计。 3.空间复杂度为S(n)级别   下程序将用递推求解斐波那契数列的第n项问题； C++；

#include <iostream>

using namespace std;

int main()
{
	
	int n;
	cin >> n;
	unsigned long long arr[n] = {1 , 1};
	for (int i = 1 ; i < n ; ++i)
	{
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	cout << arr[n - 1] << endl;
	
	return 0;
}

kitten;

教程到这里就结束了，想要看脆脆鲨编程课前面的课程请到老ZNS评论区（目前已停止运营），还有，ZNS避难营欢迎任何想要加入的新人，如果觉得这个教程好的请帮忙顶一下，谢谢