递归

1. 何为递归？

递归在我们的生活中其实很常见。假设你去电影院看电影，黑漆漆一片，你不知道自己来到了第几排，于是你问前面的人他是第几排，知道了前面的人是第几排，加一也就是你所在的排数。但前面的人也不知道，于是他也继续向前问，直到第一排的人回答他在第一排，然后再依次往后传，最后你就知道了你现在位于第几排。

• 递归可以分为两个过程，向前一直推进直到找到一个确定的解答为“递”，倒推回来得到你想要的答案为“归”。可以形象地概括为往前”递“，往后”归“。

---

2. 递归满足的条件？

• 一个问题的解可以分解为几个子问题的解。开篇的例子中，‘”自己在第几排的问题“可以分解为“前面的人在第几排”的子问题。

• 问题和分解后的子问题，除了数据规模不一样，求解思路完全一样。

• 存在递归终止条件。不能无限制地“递”下去，第一排的人知道答案后就要“归”回来。

---

3. 实现递归的关键？

• 基线条件(base case)，停止调用

• 递归条件(recursive case)， 自己调用自己

• 实现递归的关键就在于找到基线条件和递归条件。递归条件就是分解子问题的过程，基线条件就是找到递归终止的情况。

• 不要试图去弄清楚递归的详细过程，解决问题的时候要把重点放在，假设子问题已经得到解决的情况下，我们该如何求解。

---

4. 递归的注意事项？

• 重复计算。斐波那契数列，F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)。其计算过程如下所示，我们可以直观地看到有一些值被计算了很多次。
  重复计算

针对这种情况，我们可以通过定义一个数据结构（比如散列表）来保存已经求解过的值，当递归调用时，我们先查看当前值是否被计算过，如果是，则直接从散列表中取值返回，来避免重复计算。

• 堆栈溢出。递归需要多次的函数调用，而函数调用需要栈来保存临时变量，因此，当递归调用的次数非常多时，占用内存很高，就会有堆栈溢出的风险。相应的，其计算时间也可能超出想象的大。

我们可以用尾递归来确保最后一步只调用函数自身，优化堆栈使用。以求 5 的阶乘为例，尾递归的调用过程如下所示，fact_tail(5, 1) > fact_tail(4, 5) > fact_tail(3, 20) > fact_tail(2, 60) > fact_tail(1, 120)，四次递归调用后直接返回结果。

int fact_tail(int n, int a)
{
    /*Compute a factorialina tail - recursive manner.*/
     
    if (n < 0)
        return 0;    
    else if (n == 0)
        return 1;    
    else if (n == 1)
        return a;
    else
        return facttail(n - 1, n * a);
 
}

---

5. 递归与循环？

• 笼统地讲，所有递归代码都可以改为迭代循环的方式实现。

• 递归代码写起来非常简洁，程序可能更容易理解；但空间复杂度高、有堆栈溢出风险、时间成本较高。

• 改用循环，则可以减少函数调用，程序的性能可能更高，如何选择要看什么对你来说更重要。

---

获取更多精彩，请关注「seniusen」!

seniusen