递归的两种优化方法

发表于 更新于 分类于 本文字数： 658 阅读时长 ≈ 2 分钟

递归（Recursion）的两种优化方法

最近学习了一些递归的优化方法，于是想写一篇文章记录一下，方便以后查看，并想分享一下。
虽然平日的上课中老师都是建议我们不要使用递归，但是在**函数式编程（functional programming）**中递归是很常用的，而且掌握递归的思想有时能让我们找到最优解。

1. 最经典的斐波那契数列

1
2
3
4
5
6
7
8
9
int Fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    else
    {
        return Fibonacci(n - 2) + Fibonacci(n - 1);
    }
}

这个算法一般计算到 40 左右就不行了，因为运行栈已经被函数的递归调用占满了

2. 尾递归（Tail Recursive）

传说中的尾递归。具体我不细说了，就是上一个版本的优化，每次调用函数时不生成新的运行栈，利用上一次的结果
注意：不是所有语言都有尾递归优化的（Java 就没有）
也不是所有算法都能写成尾递归的形式的

1
2
3
4
5
6
7
8
int fiboTail(int n, int acc, int cal)
//acc充当收集器的左右，收集上一次运行栈的返回值，因为之后栈空间会被回收
//cal是每一次递归的计算
{
    if (n == 1) return acc;
    if (n == 2) return cal;
    return fiboTail(n - 1, cal, acc+cal);
}

可以看到尾递归的函数比原始的版本多了 2 个参数，一个起到**收集器（accumulator)**的作用，记录每上一次栈的返回值，因为原来栈的空间会被下一层递归覆盖。
还有一个参数就是每次递归的操作了，因为是斐波那契，所以这里是相加。

尾递归的调用方法也与原来的不一样，因为斐波那契的初始值 ( 1. 1 . 2 . 3 …)
所以以下的调用，acc 要用初始值 1，cal 也要用第二位的值这里也是 1
调用的方法就是 fiboTail(n, 1，1）
尾递归的方法计算基本上是秒出的，可是比起下面一种方法还是要慢，就是在 32 位机器上要注意 int 范围 第 47 位已经超过 int 的表示范围了

3. 利用缓存

典型的空间换时间

1
2
3
4
5
6
7
8
9
10
11
12
13
enum { gnFib = 99 };
int gFib[gnFib];      // 生成一个数组记录已经生成的斐波那契数

int fib(int n)
{
    if (n < 0 || n >= gnFib) return 0;
    int &fn = gFib[n];
    if (!fn) {            //如果当前数不在数组中才计算
        if (n == 0 || n == 1) fn = 1;
            else fn = fib(n - 1) + fib(n - 2);
    }
    return fn;
}

核心思想就是利用之前信息，每次递归不用再重新计算了