数据结构与算法（六）递归

首先先提出一个问题,如何用递归去求解5的阶乘,这是一个经典的递归问题.我们都知道5的阶乘求法是5×4×3×2×1.但是用编程的方式应该怎么写呢?

递归需要满足的三个条件

1,一个问题可以分解为几个子问题的解

例如求阶乘问题,每一步都可以分为n * f(n - 1).

2,子问题除了数据规模不同之外,求解思路完全一样

3,存在递归终止条件

递归是把问题一层层的分解,不能无限循环下去,这就需要一个终止条件,比如阶乘问题的终止条件就是n = 1;因为1的阶乘就是1.

求一个数阶乘的递归公式

- (NSInteger)factorial:(NSInteger)num
{
    if (num == 1) {
        return 1;
    } else {
        NSInteger tmp = num * [self factorial:num - 1];
        return tmp;
    }
}

由此我们可以看出递归的基本写法就是将问题分解为无数个相同的小问题,然后找到终止条件.

思维误区

就是用自己的脑袋去模拟算法的递归过程,绕来绕去就把自己绕晕了,人脑并不擅长做重复的事情,将这些交给计算机吧.我们只需要将问题分解找到规律即可.

练习

例:

假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？如果有 7 个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？

我们仔细想下，实际上，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了 1 个台阶，另一类是第一步走了 2 个台阶。所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：

f(n) = f(n-1) + f(n-2)

好了规律找到了,现在我们来找终止条件.当只有一个台阶的时候只有一种走法,所以f(1)= 1.但是当有2个台阶的时候,我们一步走两个台阶,这个时候台阶被走完了,可以没有触发f(1) = 1的终止条件,所以我们应该再加一个终止条件f(2) = 2,就是当有2个台阶的时候有两种走法一步一个台阶或者一步两个台阶.
那么终止条件就是f(1) = 1 和 f(2) = 2,现在规律和终止条件都有了,可以开始写代码了:

- (NSInteger)tj:(NSInteger)num
{
    if (num == 1) {
        return 1;
    }
    if (num == 2) {
        return 2;
    }
    NSInteger tmp = [self tj:(num - 1)] + [self tj:(num - 2)];
    return tmp;
}

递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等.
练习:递归
ps:内容整理自极客时间--数据结构与算法之美