具有特殊输出的java fibonacci递归方法

Question

我想用斐波那契递归方法生成一个特定的输出。我已经有了递归代码。然而，输出应该显示斐波那契数（每行一个），以及每行上当前和以前斐波那契数的比率

(if user enters 5)
Fib#1=0
Fib#2=1
Fib#3=1; 1/1=1
Fib#4=2; 2/1=2
Fib#5=3; 3/2=1 

这是我目前掌握的代码：

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

我该如何输出？我应该返回字符串还是使用不同的打印方法？谢谢

Answer 1

试试这个：

public static void main(String[] args) {
    new Main().f(5);
}

private void f(final int i) {
    if (i > 2) {
        f(i - 1);
        System.out.println(String.format("Fib#%1$d=%2$d; %2$d/%3$d=%4$d", i, fib(i-1), fib(i-2), fib(i-1)/fib(i-2)));
    } else if (i > 0) {
        f(i - 1);
        System.out.println(String.format("Fib#%1$d=%2$d", i, fib(i-1)));
    }
}

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

Answer 2

递归斐波那契输出

class FibonacciContext {
    int beforePrevious;
    int previous;

    public FibonacciContext(int beforePrevious, int previous) {
        this.beforePrevious = beforePrevious;
        this.previous = previous;
    }


    public int getBeforePrevious() {
        return beforePrevious();
    }

    public int getPrevious() {
        return previous;
    }

    public int getNext() {
        return beforePrevious + previous;
    }

    public FibonnaciContext getNextContext() {
        return new FibonnaciContext(previous, getNext());
    }
}

public FibonacciContext outputFibonacciNumbers(int maxIndex) {

    // 0 and 1 are 0 and 1 - non recursive termination
    if (maxIndex<2) {
        System.out.println(maxIndex); 
        return new FibonnaciContext(0, maxIndex);
    }

    // output all previous numbers before this one
    FibonnaciContext context = outputFibonacciNumbers(maxIndex-1);

    // print out this one
    System.out.println(context.getNext());

    // context passed back to the recursive call
    return context.getNextContext();
}

Answer 3

这个递归函数的问题是，它的效率非常低，因为它每次都需要计算整个范围。最好是循环进行

int beforeLastNumber = 1;
int lastNumber = 1;

System.out.println("0");
System.out.println("1");

for(int number=2; number<max; number++) {
    int nextNumber = beforeLastNumber + lastNumber;
    beforeLastNumber = lastNumber;
    lastNumber = nextNumber;

    System.out.println(nextNumber);
}

上面列出了我们目前所处的位置，避免了重新计算大量数字的总和以得到更高的数字

Answer 4

试试这个：

public class fib {

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

    public static void main(String[] args) {
        final List<Integer> fibList = new ArrayList<Integer>();
        int limit = 5;
        for (int i = 0; i < limit; i++)
            fibList.add(FibonnaciCalc(i));

        int tmp = 0;
        for (int i=0;i<fibList.size();i++) {
            tmp=i+1;
            if (i <2)
                System.out.println("Fib#" + tmp + "=" + fibList.get(i));
            else
                System.out.println("Fib#" + tmp + "=" + fibList.get(i)+"; "+fibList.get(i) +"/"+fibList.get(i-1)+"="+fibList.get(i)/fibList.get(i-1));
        }
    }
}