斐波那契：递归与迭代

程序员文章站 2022-06-19 11:23:40

...

我被要求解决几次的常见白板问题是“编写一个函数以从0,1开始生成第n个斐波那契数”。但是，在本文中，我想解决一个常见的跟进此问题的问题，那就是哪种方法可以更有效地解决此问题，即递归或迭代。

NOTE

最好的做法是始终尝试此问题，然后再进一步阅读本文。因此，我列出了一些用于解决此问题的常用工具。

笔/记号笔笔记本/白板VS代码互联网

斐波那契数是一个整数序列 which the first two elements are 0 & 1, and each following 元素是前面两个元素的总和：

0、1、1、2、3、5、8、13、21、34、55、89、144，...，233

The Problem

编写一个函数以生成第n个斐波那契数。第n个斐波那契数由下式给出：

Fn = Fn-1 + Fn-2
The first two terms of the series are 0, 1.
For example: fib(0) = 0, fib(1) = 1, fib(2) = 1

Solution #1 Using Recursion


public static int fibonacciRecursion(int nthNumber) {
        //use recursion
        if (nthNumber == 0) {

            return 0;

        } else if (nthNumber == 1) {

            return 1;
        }   
     return fibonacciRecursion(nthNumber - 1) + fibonacciRecursion(nthNumber - 2);
    }

Analysis

通过使用递归来解决此问题，我们得到了编写干净的函数，该函数可以进行检查。如果给定数字等于0和1，我们将返回两个给定数字。

如果传递的数字大于0和1，则进行两次递归调用，在这两个调用中将两个调用的nthNumber减去1和2进行相加。

传递这些整数0、1、2、3、4、5，很可能会及时给我们-> 0、1、1、2、3、5。

但是，如果我们传递更高的数字（例如50、67、100），会发生什么情况。那么，如果您尝试在IDE中使用给定的数字运行该函数。您将开始注意到这种方法需要花费多长时间才能获得我们的斐波那契数。现在尝试进行空间复杂性分析将是一件棘手的事情，因为在此递归函数的幕后发生了很多事情。性能不佳的原因是每次递归调用中堆栈存储器的重推式弹出。

现在，一种解决方法是使用记忆并存储以此方式计算的每个斐波那契。但是现在，我将继续使用迭代方法，以及为什么它可以更快地计算我们的第100个斐波那契数。

Solution #2 Using Iteration


 public static int fibonacciLoop(int nthNumber) {
        //use loop
        int previouspreviousNumber, previousNumber = 0, currentNumber = 1;

        for (int i = 1; i < nthNumber ; i++) {

            previouspreviousNumber = previousNumber;

            previousNumber = currentNumber;

            currentNumber = previouspreviousNumber + previousNumber;

        }
        return currentNumber;
    }