Java斐波那契递归代码

Question

我试图想出一个程序，从用户那里获取任何数字，并生成斐波那契码的第n个数字。当我完成工作时，它会显示下一个，而不是我需要的。例如，我正在寻找第11个#和它的生产233而不是144。这是我的代码：

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


public static void main(String[] args)
{
    System.out.println("Enter a Number:");
    Scanner keyboard = new Scanner(System.in);
    int number = keyboard.nextInt();
    System.out.println("You Entered Number:" + number);
    System.out.println(number + "th Fibonacci Number is:"+ fibonacci(number));
    keyboard.close();        
}

Answer 1

Aleksandar已经给了你答案，但我认为有必要提醒你，你的代码效率非常低。实际上，对于计算fibo（4），你要计算fibo（3）和fibo（2）fibo（3）将需要计算fibo（2）和fibo（1）等。最后，您将花费大量时间计算已经计算的结果（并且您将使用指数级内存来存储本地递归调用上下文）。

为了获得更高效的代码，需要实现迭代或尾部递归方法。尾部递归方法meth是一种递归调用形式为meth（f（args））的方法。在您的例子中，递归调用的形式是f（meth，args），因此它不是尾部递归的。

下面是一个尾部递归版本：

public static int fibonacci(int n) {
    if (n == 0)
        return 0;
    else if (n <= 2)
        return 1;
    else 
        return fibonacciAux(0,1,n);
}

public static int fibonacciAux(int a, int b, int n) {
    if (count == 0)
        return b;
    else  
        return fibonacciAux(b,a + b,n - 1);
}

与使用指数时间和内存的非尾部递归版本相比，该版本将以线性时间运行，并将使用恒定的内存量。

Answer 2

你缺少一个索引。您正在打印下一个斐波那契数。改变现状

(n<=0)

到

(n<=1)

编辑：

正如另一个答案所说，fib（0）=0，所以你也必须添加这个边缘情况。

Answer 3

它应该是

if(n == 0)
    return 0;
else if(n == 1)
    return 1;
else
    return fibonacci(n - 1) + fibonacci(n - 2);

因为fibonacci（0）=0