Nächste Fibonacci-Nummern generieren

Question

Ich bekam diese Frage über das Generieren von Fibonummern. Die rekursive Implementierung der Fib-Nummern, die ich gesehen habe, war immer von oben nach vorne wie fib (n) = fib (n-1) + fib (n-2), aber diese Frage geht von fib (n-1), fib (n-2) existiert als nächstes und so weiter.

public class Fibonacci { 
    int[] fiboNums; 

    public Fibonacci(int n) { 
     // TODO: generate the first n fibonacci numbers 
    } 

    private void generateNextFibo(int n, int lastFibo, int lastLastFibo) { 
     // TODO: Implement this recursive function to compute next 
     // fibonacci number. 
    } 

    public int[] getAll() { 
     return fiboNums; 
    } 
} 

Answer 1

Der erste knifflige Teil ist mit, was passierende params generateNextFibo aufgerufen werden muss. Der zweite Teil ist die Exit-Bedingung der generateNextFibo-Methode.

public class Fibonacci { 
    int fiboNums[]; 

    public Fibonacci(int n) { 
     // generate the first n fibonacci numbers 
     fiboNums = new int[n]; 
     fiboNums[0] = 1; 
     fiboNums[1] = 1; 

     // Start from 3 since the first two fibo numbers are given 
     if (n >= 3) 
      generateNextFibo(3, fiboNums[1], fiboNums[0]); 
    } 

    private void generateNextFibo(int n, int lastFibo, int lastLastFibo) { 
     // Implement this recursive function to compute next fibo number. 
     fiboNums[n - 1] = lastFibo + lastLastFibo; 
     if (fiboNums.length > n) { 
      lastLastFibo = lastFibo; 
      lastFibo = fiboNums[n - 1]; 
      generateNextFibo(n + 1, lastFibo, lastLastFibo); 
     } 
    } 

    public int[] getAll() { 
     return fiboNums; 
    } 
}