斐波拉契数列的思考

通常，斐波拉契数列通过递归实现的。比如

//Rust递归实现斐波拉契数列
fn fib(n: i32) -> i32 {
    match n {
        0 => return 0,
        1 => return 1,
        _ => return fib(n - 1) + fib(n - 2),
    };
}

fn main() {
    fib(20);
}

这一实现却是十分低效的。每次递归过程有两次递归调用，并且每次都执行重复的工作，因为fib(n) 和 fib(n - 1)都需要计算fib(n - 2)，fib(n-1) 和 fib(n - 2)都需要计算fib(n - 3)，以此类推。递归调用次数随n的增加呈指数增长。如图1所示，计算fib(5) 的递归树，包含3个相同的子树计算fib(2) 和2个相同的子树计算fib(3).

▲图1

注意到该函数有一个特点：对于给定的输入总返回相同的结果，也叫做纯函数。在计算fib(n)之后，可以保存起来，在需要的时候使用这个值。如果把前面的计算结果都缓存起来，就可以删除所有重复的子树，这样的话，求值树就如图2所示，

▲图2

这样的好处是不需要创建新的算法计算F数，甚至不知道算法是是如何运作的，只需了解相同的计算要进行多次，而且fib是纯函数，对于相同的输入计算结果相同。 

更进一步，通过代码分析可知，这是fib(n) ，fib(n-1) 和 fib(n - 2)的递推关系，某些情况下完全可以只保存两个值的缓存来替代原来的向量。

//循环 以空间换时间
fn fib(n: i32) -> i32 {

    if n == 0 {
        return 0;
    };
    let mut num1 = 0;
    let mut num2 = 1;
    for _ in 1..n {
        let tmp = num1 + num2;
        num1 = num2;
        num2 = tmp;
    }
    return num2;
}

fn main() {
     fib(20);
}