Fibonacci endrekursiv darstellen

[peterini]

Hallo,
ich soll für meinen Informatik Leistungskurs aufm gymi die Fibonacci Funktion in endrekursiver art und weise darstellen. Ich steh total auf dem schlauch irgendwie. Auf die normale rekursionsfunktion von fibonacci komme ich recht simpel, aber auf die endrekursive funktion will ich einfach nicht kommen. könnt ihr mir bitte weiterhelfen?
danke im vorraus 🙂

 

[njans]

Wie sieht denn die nicht-Endrekursive Variante bei dir aus? 🙂

 

[peterini]

hat sich erledigt 🙂 ich habs hinbekommen

 

[Marcinek]

Wie hast du es hinbekommen? - Geht das überhaupt?

Die nicht endrekursive ist klar

fib ( int x )
if (x < 2)
  return 1;
else return fib (x -1) + fib (x-2)

Der letzte Schritt wird nicht mehr durch die rekursion berechnet.

 

[musiKk]

Durch CPS sollte sich jeder rekursive Algorithmus in eine endrekursive Form umwandeln lassen.

Nebenbei: Kudos an die Schule. Bei uns war der Informatikkurs "etwas" simpler.

 

[fastjack]

vielleicht so:

    private static int fib0(int x, int y, int i, int n) {
        if (i > n)
            return y;
        else
            return fib0(y, x + y, i + 1, n);
    }
    public static int fib(int n) {
        return fib0(1, 1, 2, n);
    }

 

[Olivius]

vielleicht so:

    private static int fib0(int x, int y, int i, int n) {
        if (i > n)
            return y;
        else
            return fib0(y, x + y, i + 1, n);
    }
    public static int fib(int n) {
        return fib0(1, 1, 2, n);
    }

Da die erste Fibonaccizahl (n = 0) 0 ist, müsste der Code eher so lauten:

private static int fib0(int x, int y, int i, int n) {
    if (i > n) return y;
    else return fib0(y, x + y, i + 1, n);
}

public static int fib(int n) {
    if(n == 0) return 0;
    return fib0(1, 1, 2, n - 1);
}

 

[Olivius]

Hoffe das hat geholfen

 

[Marinek]

Denke nach 14 Jahren wirst du hier keine Antwort des to bekommen

 

[KonradN]

Hoffe das hat geholfen

Da der Thread fast 14 Jahre alt ist, bezweifle ich, dass da noch wirkliches Interesse besteht ...

Da die erste Fibonaccizahl (n = 0) 0 ist,

Das sehe ich nicht so, Das wird zwar teilweise so gesehen, aber die original Definition ist nur für n > 0 definiert und n = 0 ist einfach nicht definiert. (Sprich: n ist eine Element aus den Natürlichen Zahlen, also N und nicht N0). Die typische Definition ist halt einfach:
f(n) = f(n-1) + f(n-2) | n > 2
f(1) = f(2) = 1

Man kann das umstellen um dann auch 0 und negative Zahlen (Also n ein Element der Ganzen Zahlen, Z) ermöglichen zu können, wie es https://de.wikipedia.org/wiki/Fibonacci-Folge zeigt. Das wird aber natürlich von Deinem Code nicht abgebildet.

Das ist zumindest mein Verständnis der Fibonacci Zahlen.

Edit: Wie immer zählt aber natürlich die Aufgabenstellung selbst. Je nach konkreter Aufgabenstellung ist dann klar geregelt, was zu implementieren ist.

 

[Olivius]

Hab hier auch ne Variante mit nur drei Parametern, wenn ihr der Meinung seid, dass Fibonacci erst bei 1 beginnt, dann tauscht die 0 beim fib0-Call durch eine 1 aus

    private static int fib0(int x, int y, int n) {
        if (n < 2) return y;
        else return fib0(y, x + y, n - 1);
    }

    public static int fib(int n) {
        if(n == 0) return 0;
        return fib0(0, 1,n);
    }

 

[Olivius]

Hab hier auch ne Variante mit nur drei Parametern, wenn ihr der Meinung seid, dass Fibonacci erst bei 1 beginnt, dann tauscht die 0 beim fib0-Call durch eine 1 aus

    private static int fib0(int x, int y, int n) {
        if (n < 2) return y;
        else return fib0(y, x + y, n - 1);
    }

    public static int fib(int n) {
        if(n == 0) return 0;
        return fib0(0, 1,n);
    }

Geht auch noch kürzer:

    private static int fib0(int x, int y, int n) {
        if (n < 1) return x;
        else return fib0(y, x + y, n - 1);
    }

    public static int fib(int n) {
        return fib0(0, 1, n);
    }

 

[Olivius]

Da der Thread fast 14 Jahre alt ist, bezweifle ich, dass da noch wirkliches Interesse besteht ...


Das sehe ich nicht so, Das wird zwar teilweise so gesehen, aber die original Definition ist nur für n > 0 definiert und n = 0 ist einfach nicht definiert. (Sprich: n ist eine Element aus den Natürlichen Zahlen, also N und nicht N0). Die typische Definition ist halt einfach:
f(n) = f(n-1) + f(n-2) | n > 2
f(1) = f(2) = 1

Man kann das umstellen um dann auch 0 und negative Zahlen (Also n ein Element der Ganzen Zahlen, Z) ermöglichen zu können, wie es https://de.wikipedia.org/wiki/Fibonacci-Folge zeigt. Das wird aber natürlich von Deinem Code nicht abgebildet.

Das ist zumindest mein Verständnis der Fibonacci Zahlen.

Edit: Wie immer zählt aber natürlich die Aufgabenstellung selbst. Je nach konkreter Aufgabenstellung ist dann klar geregelt, was zu implementieren ist.

Die Fibonaccifolge ist in der On-line encyclopedia of integer sequences mit der 0 gelistet (A000045)
Dies hat auch in der Verwendung der Folge mehrere Vorteile, die dort nachzulesen sind

 

[OpaK]

Moin,

das geht auch funktional:

import java.util.function.*;

public class Main {
  static BiFunction<BiFunction, long[], Long> fib0 = (f, xyn) -> (xyn[2] < 1) ? xyn[0] : (Long)f.apply(f, new long[]{xyn[1],xyn[0]+xyn[1],xyn[2]-1});
  static Function<Character, Long> fib = n -> fib0.apply(fib0, new long[] {0,1,n});

  public static void main(String[] args) {
    System.out.println(fib.apply((char) 9));
  }
}

 

[OpaK]

Hatte das gestern nur schnell im Online-Editor getippselt, aber

es ginge auch noch ein wenig schöner und performanter mit eigenem Interface:

package temp;

import java.util.function.Function;

public interface QuadFunction<T, U, V, W, R> {
  R apply(T t, U u, V v, W w);
}

class FibHelper {
  @SuppressWarnings({"rawtypes", "unchecked"})
  private static final QuadFunction<QuadFunction, Long, Long, Integer, Long> fib0 =
      (f, x, y, n) -> n < 1 ? x : (Long) f.apply(f, y, x + y, n - 1);

  public static final Function<Integer, Long> fib = n -> fib0.apply(fib0, 0L, 1L, n);
}

class Main {
  public static void main(String[] args) {
    for (int i = 0; i <= 10; i++) {
      System.out.println(FibHelper.fib.apply(i));
    }
  }
}

Vielleicht wird das ja mal benötigt.

 

[Oneixee5]

Naja, man kann das sicherlich so schreiben - nur leider kann ich dann ein "aber" nicht vermeiden. Ich bezweifle nicht, dass das Ergebnis richtig ist. Der Weg dorthin ist aber etwas zweifelhaft. Nur mal so: Wie lange brauchst du um den Code zu verstehen und zu verifizieren? Eigentlich ist das eine ganz einfache Aufgabe und kann auch einfach und übersichtlich gelöst werden.

Nachteile:

• Versteckte Akkumulator-Technik: x und y werden mitgeschleift, um die vorherigen zwei Zahlen zu speichern.
• Künstliches Interface: Ein eigenes QuadFunction-Interface nur für den Selbstaufruf.
• Unsaubere Generics: Das Lambda muss sich selbst als Parameter übergeben, was die Type-Safety von Java aushebelt.

Der Code lässt sich mit der ungefähr gleichen Anzahl an Codezeilen viel leserlicher und intuitiv sowie sofort überschaubar umsetzen:

public class FibHelper {

    public static long fib(int n) {
        return fibHelper(0L, 1L, n);
    }

    private static long fibHelper(long x, long y, int n) {
        if (n < 1) {
            return x;
        }
        return fibHelper(y, x + y, n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.println(FibHelper.fib(i));
        }
    }
}

Das funktioniert sauber ohne Type-Cast. Wenn man sehr große Fibonacci-Zahlen berechnen will (z. B. n > 92), stößt long an seine Grenzen (Überlauf). In dem Fall lässt sich long einfach durch BigInteger ersetzen.

 

[KonradN]

Ohh Shit ... die Zombi Apokalypse startet! ... Da wird ein Thread aus 2011 erst 2025 wiederbelebt ... aber nein ... jetzt schon wieder ...

Aber immerhin haben wir jetzt einen neuen Aspekt: Tobias, der irgendwas auf Zwang funktional machen will und dann der Code diskutiert wird. Sowas hatten wir bisher noch nie 🙂

Sorry, aber das konnte ich mir jetzt nicht verkneifen ...

 

[OpaK]

der irgendwas auf Zwang funktional machen will

Es geht nicht um Zwang. Ich wollte lediglich eine zusätzliche Möglichkeit bzw. Herangehensweise/Ansatz aufzeigen. (Und hier war auch gerade nicht so viel los, und das Thema stand in der Kategorie oben. 😉) Leider treten dabei die von @Oneixee5 beschriebenen Nachteile auf.

Die Anforderungen waren: Endrekursiv (am Ende steht lediglich ein Methodenaufruf, die Berechnung steht innerhalb des Aufrufs). Dann kann man das prozedural angehen (wie es glaube ich 2025 auch getan wurde) oder funktional (wie ich es jetzt hinzugefügt hatte).

In manchen Projekten ist Absprache, alles funktional zu machen. Das sind dann Anforderungen, die solche unschönen Konstrukte mit sich bringen...

Ohh Shit ... die Zombi Apokalypse startet!

Ich bin schon ruhig.

Wenn man sehr große Fibonacci-Zahlen berechnen will (z. B. n > 92)

Für große n ... ist fast jeder der hier gezeigten Ansätze Käse. Bin mir gerade auch nicht sicher, wie man Fib. geschickt für große n berechnet. Muss ich erst eine KI fragen.

 

[Oneixee5]

In manchen Projekten ist Absprache, alles funktional zu machen. Das sind dann Anforderungen, die solche unschönen Konstrukte mit sich bringen...

Hier muss ich auch widersprechen. Funktional ist alles andere als unschön!

public class FibHelper {

    public static Stream<Long> stream() {
        return Stream.iterate(new long[]{0, 1}, pair -> new long[]{pair[1], pair[0] + pair[1]})
                     .map(pair -> pair[0]);
    }

    /**
     * n-te Fibonacci-Zahl per Stream.
     */
    public static long fib(int n) {
        return stream()
                .skip(n)
                .findFirst()
                .orElse(0L);
    }
}

Ich finde es nicht schlimm über den Code zu diskutieren, solange es sachlich bleibt. Wenn man sich mit so einem Problem beschäftigt, offenbar besteht dazu Bedarf. So kann jeder nur dazulernen.

 

[KonradN]

Sorry, aber man muss doch wirklich unterscheiden:

• effektive Umsetzung von Anforderungen
• Beispiel-Code zum Verständnis von Algorithmen.

Sorry, aber einen Algorithmus auf Zwang zu verwenden nur um dann irgendwie zu optimieren ist doch schlicht krank. Ja, natürlich kannst Du - statt einen Brief 20m entfernt in einen Briefkasten zu werfen, erst mit dem Auto zum Flughafen fahren, dann mit ganz vielen Flügen mehrfach um die Erde fliegen um dann am Ende aus Paris mit dem Taxi zu dem Briefkasten zu fahren um dann endlich den Brief einzuwerfen.

Ja, technisch geht das letztere. Und ist bestimmt interessant, dass man da dann letzten Endes 5 Mal um die Welt geflogen ist. Aber das dann zu optimieren, damit man evtl. einen Tag einspart bei den Reisen wird hoffentlich niemand als sinnvoll betrachten, wenn die Problematik ist: Der Brief soll in den Briefkasten, der 20m von Dir entfernt ist.

Und so wie es für das Briefkasten Problem eine einfache Lösung gibt (Einfach mal eben zu Fuss hin gehen und den Brief einwerfen), gibt es für Fibonacci auch einfache simple Lösungen (Die dann nicht um die Welt fliegen, also nicht Endrekursiv sind).