递归的两种优化方法

2017-10-10

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

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

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

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

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

2. 尾递归（Tail Recursive）#

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

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

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

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

3. 利用缓存#

典型的空间换时间

1
enum { gnFib = 99 };
2
int gFib[gnFib];      // 生成一个数组记录已经生成的斐波那契数
3

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