Namennutzerin
09.10.2016, 13:59
Iterative Fibonacci Methode unter der Benutzung von Stacks?

Hallo, Hab morgen Klausur und komme bei dieser Aufgabe einfach nicht auf die Lösung. Wie kann ich die rekursive Fibonacci-Methode:

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

mithilfe von Stacks iterativ implementieren?

Eine iterative Lösung hätte ich schon, aber die implementiert nicht die rekursive Vorgehensweise:

public static int fibIt (int n) { int fib1 = 0; int fib2 = 1; int fib = 0; for (int i = 1; i < n; i++) { fib = fib1 + fib2; fib1 = fib2; fib2 = fib; } return fib; }

Hat jemand vielleicht einen Vorschlag?

 ...zum Beitrag
Antwort
von Namennutzerin
09.10.2016, 14:33

Nevermind. Hab wohl zu schnell gepostet. Mir ist der Knoten jetzt aufgegangen. Für alle die diesen Post in Zukunft mal lesen hier meine Lösung: 

public static int fib (int n) {
    int current;
    int result = 0;
    Stack<Integer> stack = new Stack<Integer>();

    stack.push(n);

    while (!stack.isEmpty()) {
        current = stack.pop();
        if (current > 1) {
            stack.push(current - 1);
            stack.push(current - 2);
        }
        else{
            result += current;
        }
    }
    return result;

}
 ...zur Antwort