3. Rekursionen, wie verstehen lernen?

Rekursionen, wie verstehen lernen?

  • ?

    Hallo,

    Ich versuche schon die ganze Zeit Rekursionen zu checken, aber leider bin ich zu blöd das zu kapieren.
    Das sind die Vorlesungsfolien und ich hänge auf der Seite 118:
    http://www.pri.univie.ac.at/~itep/ws0405/EProgVO-Dateien/frame.htm

    Also da ist ein Code wie man die Fakultät rekursiv löst, ist sogar schön animiert dargestellt wie das ganze abgearbeitet wird.
    Ich verstehe die Hälfte bis return(1)

    Jetzt komm ich zum Punkt wo ich das ganze nicht mehr nachvollziehen kann also das ist an der Stelle wo n==0 und return (1) ausgegeben wird.
    Was ich da nicht verstehe ist wieso das Ding plötzlich wieder von 1 bis 3 aufsummiert?

    Kann mir das jemand in einfachen Worten erklären?

    0
  • S

    1*2*3*4*5 = 120

    wenn du nun 5! haben willst und es rekusriv löst macht man einfach eine Funktion die folgendes tut:

    prüfen ob der übergebene Parameter 1 ist, wenn ja, dann sind wir am Ende angelangt und brauchen nicht mehr uns selbst aufzurufen -> return 1
    wenn das nicht der Fall ist rufen wir uns selbst mit (parameter-1) auf

    das return 1 stellt die Abbruchbedingung da, da es sonst endlos weitergehen würde und das will man ja nicht haben.

    Ich finde auf die schnelle nicht die Erklärung auf der Seite, aber hier mal eine ausführliche Version

    int fac (int i)
{
    //speichert das Ergebnis
    int erg;

    if (i == 1)
    {
        //Erg soll 1 sein, da das Ende der Rekursion erreicht ist (also das *1)
        reg = 1;
    }
    else
    {
        //Es gibt noch etwas zu berechnen
        erg = fac (i-1); // wir rufen uns selbst mit i-1 auf
        erg = erg * i; // i*i-1 
    }

    // Das Ergebnis zurückgeben
    return erg;
}

    /Edit

    Und die Version die du am meisten antreffen wirst sieht so aus:

    int fac (int i)
{
    return i > 1 ? fac (i-1) : 1;
}
    0
  • V

    Hi!

    Vielleicht hilft dir das:
    http://www.mycsharp.de/wbb2/thread.php?threadid=2044&hilight=Rekursion&hilightuser=7

    Code-Hacker

    0
  • J

    Ich versuch mal in Worten. 😃

    Du rufst fac(3) auf. 3 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(2) * 3.
    Wichtig die Funktion (fac(3)) ist noch nicht zueende.
    Du rufst fac(2) auf. 2 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(1) * 2.
    Wichtig die Funktion (fac(2)) ist noch nicht zueende.
    Du rufst fac(1) auf. 1 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(0) * 1.
    Wichtig die Funktion (fac(1)) ist noch nicht zueende.
    Du rufst fac(0) auf. 0 == 0, d.h. du lieferst als Ergebnis das Resultat 1.
    fac(0) ist beendet.
    d.h. fac(1) liefert als Resultat 11.
    fac(1) ist beendet.
    d.h. fac(2) liefert als Resultat 2*1*1.
    fac(2) ist beendet.
    d.h. fac(3) liefert als Resultat 3*2*1    1.
    fac(3) ist beendet. ENDE

    vielleicht hilfts 🙂

    mfg JJ

    0
  • J

    Wenn schon Uni-Script dann kann ich mir folgende rekursive Version nicht
    verkneifen, da der Algorithmus nur suboptimal bzw. fehlerhaft ist ist.

    int fkt(int n)
{
  return (n <= 1) ? 1 : (n * fkt(n-1))
}

    die Original-Abbruchbedingung (n == 0) führt bei Eingabe einer negativen Zahl
    zu einer Endlosschleife. 😉

    mfg

    0
  • ?

    Dann ist deine Funktion aber auch nicht ganz fehlerlos, wenn sie für negative Argumente 1 zurückliefer 😉

    0
  • J

    Besser als ne Endlosschleife. 😃
    Ich hab auf die Schnelle nicht die Definition für negative Fakultät
    gefunden. 😞

    0
  • ?

    Danke für die schnellen Antworten!

    John Doe schrieb:

    Ich versuch mal in Worten. 😃

    Du rufst fac(3) auf. 3 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(2) * 3.
    Wichtig die Funktion (fac(3)) ist noch nicht zueende.
    Du rufst fac(2) auf. 2 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(1) * 2.
    Wichtig die Funktion (fac(2)) ist noch nicht zueende.
    Du rufst fac(1) auf. 1 != 0, d.h. du lieferst als Ergebnis das Resultat von fac(0) * 1.
    Wichtig die Funktion (fac(1)) ist noch nicht zueende.
    Du rufst fac(0) auf. 0 == 0, d.h. du lieferst als Ergebnis das Resultat 1.
    fac(0) ist beendet.
    d.h. fac(1) liefert als Resultat 11.
    fac(1) ist beendet.
    d.h. fac(2) liefert als Resultat 2*1*1.
    fac(2) ist beendet.
    d.h. fac(3) liefert als Resultat 3*2*1    1.
    fac(3) ist beendet. ENDE

    vielleicht hilfts 🙂

    mfg JJ

    Thx, das hat mir ein wenig weitergeholfen, ich dachte immer die Fkt wird nach jedem else Zweig beendet...
    Aber das Prob ist wie kommt man selbst auf eine Rekursion? 😕
    Die Funktionsweise einer Rek versteh ich einigermaßen, wird irgendwie von "hinten nach vorne" abgearbeitet und wiederum von "vorne nach hinten" ausgegeben. 😃
    Oder man kann sich einen Stapel Bücher vorstellen, die von unten nach oben aufgestapelt wird und wieder von oben nach unten abgearbeitet.

    Was aber das Prob bei mir ist, ich seh das im Code irgendwie nicht, wieso nach return 1 wieder die funktionen von 1 bis n aufgerufen werden.

    0
  • J

    Na dann hast du aber mächtig Probleme wenn du Quicksort() verstehen sollst. 😃

    mfg JJ

    0
  • V

    Hi!

    @John Doe:
    Es gibt keine negative Fakultät. Würde -1 oder 0 zurückgeben, um so einen Fehler zu signalisieren. Habe dazu mal SirLants-Lösung modifiziert:

    int fac (int i)
{
    return (i > 1) ? fac (i-1) : (i<0) ? 0 : 1;
}

    Code-Hacker

    0
  • T

    Und warum nicht einfach

    unsigned fac(unsigned n)
{
  return fac <= 1 ? 1 : n * fac(n-1);
}
    0
  • T

    Laserstrahl schrieb:

    Was aber das Prob bei mir ist, ich seh das im Code irgendwie nicht, wieso nach return 1 wieder die funktionen von 1 bis n aufgerufen werden.

    Bei den meisten Rekursionen verwirrt es nur, wenn man versucht, sich alle Aufrufe
    vorzustellen. Überlege dir einfach: Was macht ein Aufruf?

    Angenommen, du willst die n! berechnen und kennst (n-1)!. Das Ergebnis ist dann
    doch offensichtlich n! = n * (n-1)!, es sei denn, n ist 1 oder 0, dann ist
    n! = 1. Mehr steht da nicht.

    Wenn du das geschluckt hast, kannst du anfnagen, dir über Bücherstapel Gedanken
    zu machen: Wir haben nämlich nur angenommen, wir würden (n-1)! kennen. Tun
    wir aber gar nicht. Dann müssen wir das eben berechenen. Wir berechnen also
    (n-1)!, und weil sich das blöd schreibt, (n-1)! = m!. Und dann stehen wir wieder
    Und wenn wir nu m! berechnet haben (in dem wir uns selbst aufgerufen haben; dabei vergessen wir, dass es mal um n! ging und kümmern uns nur um m!),
    können wir auch n! berechnen.

    0
  • V

    Hi!

    Ja, ist natürlich besser gleich gar keine negativen Zahlen zuzulassen, ansonsten sollte man diesen Fall allerdings abfangen.

    Code-Hacker

    0
  • M

    Guten morgen,

    ich versuch Mal ein Beispiel hinzuschreiben.
    Wie gesagt:
    n! = n*(n-1)!, wobei ! natürlich einen höheren Rang als * hat.

    5! wird also zu:

    5*4!

    und 4! wird zu:

    4*3!

    also wird 5! zu:

    5*4*3!

    daraus ergibt sich auf Dauer:

    5*4*3*2

    MfG Eisflamme

    0
  • ?
     

    #include <iostream>

using namespace std;

double fac(double n)
{
  return n > 1 ? n*fac(n-1) : true;
}

int main()
{
  cout << fac(6) << endl; // Warum 720  und nicht 1 ?
}

    warum wird hier 720 zurückgegeben und nicht 1(true) ?

    0
  • S

    hmm ? schrieb:

    #include <iostream>

using namespace std;

double fac(double n)
{
  return n > 1 ? n*fac(n-1) : true;
}
 
 
int main()
{
  cout << fac(6) << endl; // Warum 720  und nicht 1 ?
}

    warum wird hier 720 zurückgegeben und nicht 1(true) ?

    Weil 6! 720 ist, weshalb sollte da ne 1 ausgeben werden?

    0
  • O
     

    double fac(double n)
{
  return n > 1 ? n*fac(n-1) : true;
}

    da sieht man wieder wie schön die typentrennung misachtet wird.

    übrigens kommt da nur ne 1 raus wenn n nicht größer als 1 ist und das nur deshalb weil true für ne 1 steht in c++ ...so nen code sollte man sich nicht angewöhnen!

    0
Anmelden zum Antworten