[F481]

Hallo, ich habe hier 2 Funktionen, die beide den Binomialkoeffizienten "n über k" berechnen.
Die eine Funktion ist rekursiv gelöst, die andere nicht rekursiv. Für große Werte (bspw. n=20 k=10) bekomme ich unterschiedliche Ergebnisse.. kann mir jemand erklären woran das liegt?

rekursive Funktion:

int binomialCoefficient( int n, int k ) {
    if (n < 0 || k < 0 ){
        return -1;
    }
    if ( k == n || k == 0 ){
        return 1;
    }
    return binomialCoefficient(n-1,k) + binomialCoefficient(n-1, k-1);
}

nicht rekursive Funktion:

int faktorial(int n) {
    if (n == 0 || n == 1 ) {
        return 1;
    }
    else {
        return n*faktorial(n-1);
    }
}

int binominalCoefficient(int n, int k) {
    // n oder k negativ?
    if (n < 0 || k < 0 ){
        return -1;
    }
    if ((0 <= n) && (n < k)) {
        return 0;
    }
    return faktorial(n)/(faktorial(k)*faktorial(n-k));
}

Dieser Beitrag wurde von F481 bearbeitet: 26. Juni 2014 - 15:42

[RalphS]

Mh? Die sind doch beide rekursiv: eine verschränkt und die andere nicht.

Werd mal drübergucken, sobald ich dazu komme, ob ich da nen Haken drin finde.

---

Riecht mir stark nach Überlauf. Probier mal was Größeres als int.

PS. Ich hoffe einfach mal, daß es hier eher um Proof-of-Concept oder sowas geht. Die Methode hier ist ARG ineffizient - wenn möglich, ist JEDE Rekursion zu vermeiden und wenn das nicht geht, muß man schauen, wo der Speicherplatz bleibt.

Dieser Beitrag wurde von RalphS bearbeitet: 26. Juni 2014 - 16:15

[F481]

Danke, ja die Aufgaben waren nur als Übung für Rekursion gedacht. Bei einem Überlauf würde doch eher Blödsinn rauskommen oder?
Die Ergebnisse weichen eher voneinander ab, als dass sie völlig daneben sind.

P.S. Rekursion kann manchmal auch ganz praktisch sein, siehe Turme von Hanoi

[RalphS]

Nicht in der Informatik: Alles was ohne Rekursion geht, wird auch ohne gemacht. Warum den Aufwand? Ob ich jetzt 1+2+3+4+5+...+n rechnen lasse oder die geschlossene Formel nehme, es kommt dasselbe bei raus; aber der Aufwand ist um LÄNGEN geringer.

... Ist das vielleicht Numerik, was Du da grad machst? Jedenfalls, je nach Implementierung ist es natürlich möglich, daß das eine überläuft und das andere nicht und/oder daß beide unterschiedlich überlaufen. Welche Variante rechnet denn (wenn überhaupt eine) das *richtige* Ergebnis aus?

[ndeath]

Also ich kann nicht programmieren...aber was folgende soll ist mir nicht klar:

return binomialCoefficient(n-1,k) + binomialCoefficient(n-1, k-1)

[Sturmovik]

Ähm, ich hab jetzt nicht so den Plan von C, aber mir kommen die Verzweigungen komisch vor.

Ist return gleichzeitig zur Zuweisung auch das Ende der Funktion?
Wenn nicht, dann gilt ja immer das letzte return der Funktion, egal, ob die if-Clauses davor wahr sind oder nicht.

[RalphS]

ndeath: Rein funktional haut das schon hin: es soll das Ergebnis von Funktion 1 *plus* dem Ergebnis von Funktion 2 zurückgegeben werden. Daß diese identisch sind und rekursiv aufgerufen werden... paßt soweit, *solange* wie sichergestellt wird, daß das *irgendwann* terminiert. Sonst legt das irgendwann den Rechner lahm.


Abgesehen vom von mir oben geschriebenen... ist mir der Ansatz auch noch ein wenig - und ich bitte das Wort zu verzeihen -naiv.

Denn wie erwähnt, das Abbruchkriterium ist bei Rekursionen das A und O und das wird nicht sauber geprüft, sodaß wenn man da aus Versehen was blödes eingibt (und darunter zählen eben auch Rekursionszwischenergebnisse!) da dann sonstwas bei rauskommt.

- n und k sollen unsigned sein. Das kann man sicherstellen. Ganzzahlig sind sie ja schon; mit unsigned sind sie natürlich.
- WENN beide unsigned sind, kann man das mathematisch bestimmen und muß nicht auf UND/ODER zurückgreifen. Wenn n - k = 0, heißt das zum Beispiel, daß da 1 rauskommen muß. Dann braucht man nicht rechnen. Dasselbe für n + k < 3; dann waren n und k so belegt, daß das Ergebnis immer noch recht klar ist.
- Was ist in der verschränkten Funktion (#1) wenn k > n? Und was in der anderen?


Man soll das ja als Quelle meiden, aber belesen kann man sich bei Wikipedia durchaus. Die haben unter dem Begriff auch einen Algoritmus angegeben, wie man das effektiv hinkriegt.

Dieser Beitrag wurde von RalphS bearbeitet: 26. Juni 2014 - 20:56