递归和迭代(又叫递推)是两种不同的计算方法，它们在处理问题时有各自的优势和局限性。
递归是一种自顶向下的计算方法，它将问题分解为更小的子问题，然后通过递归调用自身来解决这些子问题。递归的优点是代码简洁、易于理解，但缺点是计算效率较低，尤其是在处理大量数据时，因为每次递归都需要保存之前的计算结果，导致空间复杂度较高。
迭代是一种自底向上的计算方法，它从问题的初始状态开始，逐步解决问题的各个部分，直到达到最终目标。迭代的优点是计算效率较高，尤其是在处理大量数据时，因为不需要保存之前的计算结果，空间复杂度较低。但缺点是代码相对复杂，不易理解。
以斐波那契数列的计算为例：
斐波那契数列是一个典型的递归问题，其定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2),其中 n > 1
使用递归实现斐波那契数列的方法如下：
```c
uint64_t Fibonacci(unsigned char n) {
if( n == 0 ) return 0;
if( n == 1 ) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
```
这个代码虽然简单，但是计算复杂度却太高。当 n稍微大一点时，计算时间就会非常长。为了降低时间复杂度，我们可以将递归算法改为递推算法：
```c
uint64_t Fibonacci(unsigned char n) {
if( n == 0 ) return 0;
if( n == 1 ) return 1;
uint64_t f[3] = {0, 1}; // 用数组存储中间结果
uint64_t result = f[2]; // 从第三个元素开始计算
int i; // 用循环代替递归调用
for(i = 2; i <= n; i++) // 从第三个元素开始计算到第n个元素
{
result = f[i-1] + f[i-2]; // 根据斐波那契数列的定义计算下一个元素的值
f[i] = result; // 将计算结果存入数组中
}
return result; // 返回最终结果
}
```
这个程序很简单，for循环中计算了n−2次，所以时间复杂度为 O(n)。使用递推时，如果要计算第100个数，那么要先直到第99和第98个，要知道第99个和第98个，就要分别进行递归，直到最后一层，再返回递归回来进行计算。
在计算斐波那契数列时，可以使用迭代方法，即从前往后进行循环计算。首先确定前两个数，然后根据这两个数计算出第三个数。接着将第三个数和第二个数重新赋值给之前的变量，并继续相加。需要注意的是，迭代方法每次都需要重新计算，这可能会导致效率较低。
为了提高效率，我们可以考虑将已经计算过的结果用链表保存起来。这样，在需要计算某个位置的斐波那契数时，我们可以先在链表中查找是否已经有该位置的结果，如果有，则直接返回；如果没有，则进行计算并将结果添加到链表中。这种方法被称为动态规划(Dynamic Programming),可以在一定程度上减少重复计算，提高效率。
