算法之递归和迭代
递归和迭代（又叫递推）的区别，参考：
迭代与递归的区别_递归和迭代的区别-CSDN博客
示例参考：
笔记-迭代代替递归（Fibonacci小例）-CSDN博客
Fibonacci 数列及其计算方法_fibonacci数列-CSDN博客
迭代其实就是把之前的数给存下来，而递归每次都是从头到尾硬算，不会保留之前的计算结果。
以Fibonacci数列的计算为例
Fibonacci 数列及其计算方法
斐波那契数列（Fibonacci sequence），又称黄金分割数列，这个数列最早是由印度数学家提出来的。不过更多的人学习到这个数列是因为意大利数学家列昂纳多·斐波那契（Leonardoda Fibonacci）和他的《Liber Abaci》一书。在这本书中，列昂纳多·斐波那契以兔子繁殖为例子引出了这个序列，因此这个序列又称为“兔子数列”。
这个序列的前几项是这样的：0,1,1,2,3,5,8,13,21,34,⋯
在数学上，斐波纳契数列以如下被以递归的方法定义：
程序实现 斐波纳契数列的定义是递归形式的。自然，用递归函数最容易实现。
uint64_t Fibonacci(unsigned char n)
{if( n == 0 ) return 0;if( n == 1 ) return 1;return Fibonacci(n - 1) + Fibonacci(n - 2);
}这个代码虽然简单，但是计算复杂度却太高。当 n稍微大一点时，计算时间就会非常长。
如果将递归算法改为递推，时间复杂度会降低很多。
uint64_t Fibonacci(unsigned char n)
{if( n == 0 ) return 0;if( n == 1 ) return 1;uint64_t fn, fnn = 1, fnnn = 0;for(int i = 2; i <= n; i ++){fn = fnn + fnnn;fnn = fn;fnnn = fnn;}return fn;
}这个程序很简答，for 循环中计算了n−2次， 所以时间复杂度为 O(n)
使用递归时，如果要计算第100个数，那么要先直到第99和第98个，要知道第99个和第98个，就要分别进行递归，直到最后一层，再返回递归回来进行计算。
如果是用迭代，那么就是用循环从前往后计算，前两个数是固定的，先根据前两个数可以计算出第三个数，然后把第三个数和第二个数再赋值给之前的变量，再相加即可。迭代这里也是每次都重新计算，如果我把已经计算过的结果用链表保存起来，那是不是更好呢？