求斐波那契数列第n项的值

求斐波那契数列第n项的值

这是一道常规的面试题目，以此题目来说明递归可能会增加计算的次数，造成性能浪费。可以把递归转换成循环的方式对递归算法进行优化。

求Fibonacci(30)

常用来考递归的思考方式，因为递归看起来比循环高那么一点点，可实际上循环才是这道题的最优解法。递归的写法模式是前面写退出条件，后面写递归调用。

递归写法 

public static int FibonacciRecursive(int n)
{
    if (n < 1)
    {
        throw new Exception("参数必须大于0");
    }

    if (n == 1 || n == 2)
    {
        return 1;
    }

    return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}

循环写法

public static int FibonacciLoop(int n)
{
    if (n < 1)
    {
        throw new Exception("参数必须大于0");
    }

    if (n == 1 || n == 2)
    {
        return 1;
    }

    var x = 1;
    var y = 1;
    var result = 0;
    for (var i = 3; i <= n; i++)
    {
        result = x + y;
        x = y;
        y = result;
    }

    return result;
}

Fibonacci(30) = 832040

递归调用没有记录中间计算的FibonacciXXX(n)结果，每一次都要重新计算，重复计算造成性能浪费。

写递归算法的时候，有意识地尝试转换成循环，如有性能优化就进行优化。

过度优化代码

有人会将循环写法写成下面形式：

public static int FibonacciLoop(int n)
{
    if (n < 1)
    {
        throw new Exception("参数必须大于0");
    }

    var x = 1;
    var y = 1;
    var result = 1;
    for (var i = 3; i <= n; i++)
    {
        result = x + y;
        x = y;
        y = result;
    }

    return result;
}

代码量的确比原来的代码少了,但是可读性也是降低了。

更有甚者，优化成下面形式：

public static int FibonacciLoop(int n)
{
    if (n < 1)
    {
        throw new Exception("参数必须大于0");
    }

    var x = 1;
    var y = 1;
    for (var i = 3; i <= n; i++)
    {
        y = x + y;
        x = y - x;
    }

    return y;
}

这个代码更难理解了，应避免这样的过度优化代码。

打赏