Anzeige:
Ergebnis 1 bis 8 von 8

Thema: Rekursion verständlich

  1. #1
    Registrierter Benutzer
    Registriert seit
    25.02.2002
    Ort
    2nd level cache
    Beiträge
    90

    Question Rekursion verständlich

    Hallo!

    Gibt es hier auf diesem Planeten irgendeinen Menschen, der mir Rekursion mal
    verständlich erklären kann? Ich stehe am Rande der Verzeiflung
    Das ist mir irgendwie zu abstrakt.

    Am liebsten in C++ am Besipiel 2^x

    Habe die Suchfunktion schon bemüht und gefunden, aber leider nicht verstanden.

    Für Hilfe dankbar

    GreetZ

    ReSeT
    Einmal schwarzen Tee mit Milch und Zucker bitte!

  2. #2
    Administrator Avatar von anda_skoa
    Registriert seit
    17.11.2001
    Ort
    Graz, Österreich
    Beiträge
    5.477
    Code:
    int zweiHochX(int x)
    {
        if (x == 0)
            return 1;
        if (x == 1)
            return 2;
        return 2*zweiHochX(x-1);
    }
    Rekursion ist ein verschachtelter Aufruf.
    Die Funkiton zweiHochX ruft sich selbst wieder auf, bis eine der beiden Abbruchbedingungen erfüllt ist.

    Das "sieht" im Prinzip so aus

    Code:
    y = zweiHochX(3);
           
    // wird dann zu
    y = zweiHochX(2*zweiHochX(2));
    
    y = zweiHochX(2*(2*zweiHochX(1)));
    
    y = zweiHochX(2*(2*(2)));
    
    y = 8;
    Ciao,
    _
    Qt/KDE Entwickler
    Debian Benutzer

  3. #3
    Registrierter Benutzer
    Registriert seit
    27.11.2002
    Ort
    München
    Beiträge
    5
    aber belasten viele rekursionen nicht den speicher ? ich kann mich noch an DOS-zeiten erinnern (nicht schlagen ), wenn man da zu viele rekursionen gemacht hat, ist das system gestorben.
    so hatte ich einmal eine quicksort-implementierung (der ja auch mit rekursion sortiert) und ab ca 500 elementen war schluss

    unter linux hab das ding mal mit 100.000 elementen gemacht und es gab keine probleme. wo liegen die grenzen der rekursionen ?
    Totale Paranoia ist totales Bewußtsein

  4. #4
    Registrierter Benutzer Avatar von Headcrash23
    Registriert seit
    02.11.2002
    Beiträge
    8
    Rekursionen belasten den Stack.
    Damals (in den DOS-Zeiten) hatten die PCs noch nicht soviel Speicher, und deshalb bist du da recht schnell rausgeflogen.

    Rekursion wird meistens anhand von einfachen Beispielen erklärt, doch sollte auch darauf hingewiesen werden, in der Praxis lieber eine gleichwertige iterative Lösung zu wählen... sofern sie vorhanden ist (um den Stack zu entlasten).

    Zwei hoch x geht z.B. auch iterativ mit einer For-Schleife.

    Bei komplexeren Fragestellungen kommst du häufig nicht an der Rekursion vorbei (Bäume etc.).

  5. #5
    Registrierter Benutzer
    Registriert seit
    27.11.2002
    Ort
    München
    Beiträge
    5
    Danke für die Info. Wenn ich wissen will, wieviele Rekursionen gehen, einfach ausprobieren, bis das Programm rausfliegt ? Oder brauch ich mir mit 256 MB einfach keine Sorgen machen, solange ich im "normalen" Bereich wiederhole ?
    Totale Paranoia ist totales Bewußtsein

  6. #6
    Administrator Avatar von anda_skoa
    Registriert seit
    17.11.2001
    Ort
    Graz, Österreich
    Beiträge
    5.477
    Die meisten Rekursionen können als Iteration aufgelöst werden.
    zB in dem man explizit einen eigene Stack am Heap benutzt, der dann weiter wachsen kann.

    Bei sogenannten tail-recursive Funktionen, können das sogar gute Compiler auflösen.

    tail-recursive ist eine Funktion, wo die Rekursion die letzte Operation ist.
    Wie in meinem obigen Beispiel.

    Ciao,
    _
    Qt/KDE Entwickler
    Debian Benutzer

  7. #7
    Registrierter Benutzer
    Registriert seit
    25.02.2002
    Ort
    2nd level cache
    Beiträge
    90
    Hatte völlig verschwitzt mich für eure Antworten zu bedanken
    Hab's jetzt mit der Rekursion wohl begriffen.

    Bis denne

    Greetz
    reset
    Einmal schwarzen Tee mit Milch und Zucker bitte!

  8. #8
    Registrierter Benutzer
    Registriert seit
    03.07.2002
    Beiträge
    21
    Moin!

    Um Rekursionen zu verstehen, muss man erstmal Rekursionen verstehen

    SCNR,

    iGEL

Lesezeichen

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •