递归斐波那契代码

Question

我已经按照以下方式编写了斐波那契数列。我想知道是否下面的递归使用方式是正确的，因为我认为我正在使用类似于for循环的条件和递增值来循环斐波那契函数。

public class FibanocciSeriesImpl {
static int a,b,i,n;
    static
    {
        a=0; b=1;i=2;
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the number of elements in the series");
        n=sc.nextInt();

    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("The fibnocci series is below");
        System.out.print(a+","+b);
        fibnocciImpl(a,b);
    }
    public static void fibnocciImpl(int a,int b)
    {
        int c=a+b;
        a=b;
        b=c;
        i++;
        System.out.print(","+c);
        if(i<n)
        fibnocciImpl(a,b);

    }
}

- Sawyer

---

这不是斐波那契数列递归函数的经典实现，但根据定义，由于在函数内部调用自身，因此它是递归。 - Blake Lockley

Answer 1

斐波那契序列可以用递归实现，只需要两行代码，就像这样：

public static long fib(int n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

请注意这不是计算斐波那契数列最有效的方法，尽管从代码角度来看这可能是最简单直接的。我会让你自己实现更高效的方法。

- MeetTitan

Answer 2

虽然这个问题已经被提及很多次，但值得重复强调：按照定义递归计算斐波那契数列——不使用记忆化等技术——需要指数级时间（类似于 O(1.6^n)），对于较大的 n（如 n>40）来说是不可行的。

斐波那契数列也可以通过迭代方式在线性时间内计算。

public static long fib(int n) {
    long a = 0, b = 1;
    if (n <= 1) { return n; }
    for (int i = 2; i < n; ++i) {
        int tmp = b;
        b += a;
        a = tmp;
    }
    return b;
}

就算价值不高，这里也有同样的算法使用 Brainfuck 编写（源自我高中时期）：

++++++++++ > + ; N i j 
< ; point to N 
[
    > ; move pointer to i
    [ >> + > + <<< - ] ; add i to t1 and t2
    > ; move to j
    [ < + > - ] ; add j i 
    >> ; move to t2
    [ << + >> - ] ; add t2 to j 
    < ; move to t1
    [ >> + << - ] ; add t1 to t3
    >> ; move to t3 
    [ < + < + >> - ] ; move t3 to t1 and t2
    <<<<< -
]
>>> .

- blazs

---

最朴素的递归方式可能需要指数级时间，但也可以以线性时间递归实现。 - marstran

@marstran 当然，我的意思是，按照定义（且没有记忆化）计算需要指数时间。 - blazs

这是一个递归解决方案，没有记忆化，在线性时间内完成（使用Scala因为空间原因）：def fibonacci(first: Int, second: Int, n: Int) = if (n <= 0) first else fibonacci(second, first + second, n - 1)。 - marstran

@marstran，很好，我知道这些简单的事实。我只是指出OP使用的特定递归函数需要指数时间。 - blazs

Answer 3

也可以使用动态规划实现斐波那契数列，这比递归更有效率。

int fibonacci(int n) {

    int[] f = new int[n + 1];
    int i;

    f[0] = 1;
    f[1] = 2;

    for (i = 2; i < n; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

    return f[i - 2];
}

时间复杂度：O（n） 额外空间：O（n）

- Maytham Fahmi

---

如果您只使用最后两个值，则没有必要创建数组。两个本地变量就足够了。 - Paul Boddington

@paulboddington 我同意你的观点，但这只是为了向 OP 展示可能性。 - Maytham Fahmi

Answer 4

public static void printFIBO(int n) {
    System.out.println(n <=1 : n ? fib(n-1) + fib(n-2));
}

- user5961012

---

这个无法编译。抱歉，伙计 :( - MeetTitan

printFIBO 返回 void，这意味着你不应该从中返回任何东西。另外，System.out.print(String) 将字符串写入 stdout，并且也返回 void，这意味着——你猜对了——它不返回任何值。因此，你不能从不返回任何内容的函数中返回一个不存在的值。非常接近了！ :) - MeetTitan

虽然这段代码可能回答了问题，但提供关于它是如何解决问题的额外上下文信息会提高答案的长期价值。 - Michael Parker

Answer 5

是的，这是递归，但又不是递归。 :)

之所以是递归，是因为你在再次调用函数，但你误用了递归；你只是把循环替换成了递归调用。

这里有一个简单的例子，将循环改为递归：

for(int i = 0; i < 3; i++) {
    // do something
}

可以被替换为

  i = 0; // global variable
           //so that it maintains the value during recursive function calls
    void func() {
        // do something
        if(i < 3)
            func();
        i++;
    }

但是好的递归是使用相同的函数做一些有意义的事情。

这是斐波那契数列的受欢迎的实现：

public static long fib(int n) {
    if (n <= 1) return n;
    else return fib(n - 1) + fib(n - 2);
}

注意我们如何通过调用自身使函数计算自身，并让终止条件发挥作用！因此，当 n = 0 或 1 时，它将返回这些数字作为计算的种子给立即的调用者。

所以 fib(1) = 1 和 fib(2) = 2... 当我们在递归堆栈中返回时，fib 被计算出来了。

请注意，自上而下的计算方法是指数级别的，但是记住已计算的 fib（动态规划）的自下而上的方法是 O(n)，并且更加高效。

- Sameh

Answer 6

你可以用递归的方式来实现：

int fib(int i){
if(i == 0 || i ==1) return n;
else return fib(i - 1) + fib(i-2);
}

但更快的方法是使用迭代方式，您可以在此处阅读示例：

迭代 vs 递归

- FoldFence