Rekursion - Hilfe bei der Umsetzung

Bashar

@wob sagte in Rekursion - Hilfe bei der Umsetzung:

Radius klingt nach Kreis - was soll da eigentlich berechnet werden?

$\sum_{n=0}^N 3^n \pi \left ( \frac{r}{2^n} \right ) ^2$ , sieht aus wie aus Ramanujans Notizbuch.

Jockelx

@john-0
Da steht, dass man sich etwas in der Schleifen merken muss, was durch eine Rekursion ggf. überflüssig wäre.
Dein Text passt nicht zur Antwort.

SeppJ

@john-0 sagte in Rekursion - Hilfe bei der Umsetzung:

@SeppJ sagte in Rekursion - Hilfe bei der Umsetzung:

Die wahre Absicht ist natürlich, dass man irgendetwas erkennt, dass sich rekursiv sehr viel einfacher schreiben lässt als mit Schleifen. Das typische Zeichen, dass es eine bessere Rekursion geben kann, ist wenn sich ein Schleifendurchgang irgendwo ein Ergebnis für einen späteren Durchgang merkt.

Und genau das ist das Anzeichen, dass man Rekursion besser nicht nutzen sollte, da jedes „Merken“ ein Anwachsen des Stacks pro Rekursionsschritt bedeutet. Wenn die Rekursionstiefe nicht unter Kontrolle ist, läuft man Gefahr das der Stack explodiert. Dagegen sind Schleifen in dieser Hinsicht gutmütig und erzeugen kein unkontrolliertes Anwachsen des Stacks.

Und was ist mit dem Platz, wo du dir das bei den iterativen Schritten merkst? Der Unterschied ist lediglich, dass du in einem Fall den Platz explizit auf den Stack der Funktion packst, in der deine Schleife lebt, und im anderen Fall er implizit auf den Callstack der einzelnen Unterfunktionen angelegt wird. Zumindest wenn du solch eine dumme Schema-F Transformation benutzt, wie ich sie oben gezeigt habe. Da Rekursion hier keinen Vorteil hat und nur kompliziert zu schreiben ist, würde ich hier aber auch von abraten.

Der Vorteil der Rekursion ist jetzt aber, dass man die Option hat einen Space-Time-Tradeoff zu machen, indem man das Problem so umschreibt, dass man weniger der zeitintensiven Schritte braucht, unter dem Tradeoff dass dazu alle Zwischenergebnisse gleichzeitig im Speicher liegen müssen. Vorausgesetzt, das Problem ist so zerlegbar. Das ist praktisch immer das richtige Vorgehen, denn Zeit ist in typischen Computersystemen viel wichtiger als Platz. Man muss da halt als Programmierer mitdenken, verstehen, und abwägen. Das ist es, was einen Programmierer ausmacht. Zumindest solche, die höhere Ambitionen haben, als Codezeilen nach Vorgabe zu tippen. Dazu muss man es natürlich auch üben an Beispielen, die man unter kontrollierten Bedingungen verstehen kann, aus Fehlern lernen, und auf gar keinen Fall die Technik kategorisch aus Unwissen ablehnen.

Die meisten akademischen Beispiele sind leider sehr unbefriedigend, weil die Problemstellungen entweder sehr künstlich sind, oder aber überhaupt nicht gut geeignet sind zur Zerlegung mittels Rekursion - so wie hier. Daher hat sie einen schlechteren Ruf, als sie verdient. Aber sie ermöglicht halt auch massive Zeiteinsparungen, wenn richtig eingesetzt.

PS: Ich habe leider auch keine Hammerbeispiele. Nimm eine binäre Suche, oder jeden anderen Algorithmus, der mit Bäumen arbeitet: Es ist derart offensichtlich, dass man dies rekursiv angehen sollte, dass man gar nicht mehr anders über diese Probleme nachdenken kann. Selbst wenn ein typischer Programmierer dies heute mit einer Schleife nachprogrammiert, emuliert er doch nur die Rekursion, indem man sich einen Pseudo-Stack baut, in welchem Frame er gerade sucht. Aber irgendwann am Anfang der Informatik hat jemand mal gesagt: "Was ist wenn ich nicht einfach nur Wert für Wert durch die Sequenz durchgehe? Sondern in immer kleineren Fenstern, aufeinander aufbauend. Das kostet mich ein paar mehr Variablen aber ich bin viel schneller fertig". Und das war ein großartiger Gedankenschritt.

PPS: Es ist für die Laufzeitkomplexität (und die Speicherkomplexität auch) natürlich egal, ob man Schleifen mit Zwischenwerten oder "echte" Rekursion benutzt. Und umgekehrt. Weil sich alles äquivalent ineinander umformen lässt. Es ging mir darum, dass man durch die andere Denkweise Vereinfachungen der Problemstellung an sich erkennen kann, und dadurch dann massive Verbesserungen gegenüber naiveren Algorithmen gewinnen kann.

*john 0

@SeppJ sagte in Rekursion - Hilfe bei der Umsetzung:

Und was ist mit dem Platz, wo du dir das bei den iterativen Schritten merkst? Der Unterschied ist lediglich, dass du in einem Fall den Platz explizit auf den Stack der Funktion packst, in der deine Schleife lebt, und im anderen Fall er implizit auf den Callstack der einzelnen Unterfunktionen angelegt wird. Zumindest wenn du solch eine dumme Schema-F Transformation benutzt, wie ich sie oben gezeigt habe. Da Rekursion hier keinen Vorteil hat und nur kompliziert zu schreiben ist, würde ich hier aber auch von abraten.

Wenn man Schleifen benutzt und pro Iteration Speicher benötigt, muss man sich vorher Gedanken machen, wie man diesen Speicher alloziert. Diese Allokation erfolgt dann auf dem Heap. Der Vorteil des Heaps war und ist, dass ich dort viel einfacher große Speicherblöcke allozieren kann. Vielfach kann man noch nicht einmal den Stack aus dem Programm heraus ändern, und mit C++ eigenen Funktionen gleich gar nicht. Aber die typische Stackgröße ist winzig in Relation zum Heap. Die Stackgröße ist zwar im Laufe der Zeit besser geworden, aber das Verhältnis zwischen Stack und Heap hat sich nicht verändert.

Die meisten akademischen Beispiele sind leider sehr unbefriedigend, weil die Problemstellungen entweder sehr künstlich sind, oder aber überhaupt nicht gut geeignet sind zur Zerlegung mittels Rekursion - so wie hier. Daher hat sie einen schlechteren Ruf, als sie verdient. Aber sie ermöglicht halt auch massive Zeiteinsparungen, wenn richtig eingesetzt.

Wie wäre es mit Quicksort? Das ist weder akademisch noch unrealistisch. Wenn man nun das Feld richtig groß macht, und das sortieren will, sieht man sofort den Unterschied.

PS: … Aber irgendwann am Anfang der Informatik hat jemand mal gesagt: "Was ist wenn ich nicht einfach nur Wert für Wert durch die Sequenz durchgehe? Sondern in immer kleineren Fenstern, aufeinander aufbauend. Das kostet mich ein paar mehr Variablen aber ich bin viel schneller fertig". Und das war ein großartiger Gedankenschritt.

Das erinnert mich fatal an meine Mathematikvorlesung. Der Professor ganz Mathematiker hat mit absoluter Detailfreude uns den Beweis angeschrieben, dass das lineare Gleichungssystem lösbar sei. Aber den Gauß-Algorithmus hat er dann irgend wie in eine Ecke das Tafel hingeschmiert.

PPS: Es ist für die Laufzeitkomplexität (und die Speicherkomplexität auch) natürlich egal, ob man Schleifen mit Zwischenwerten oder "echte" Rekursion benutzt. Und umgekehrt. Weil sich alles äquivalent ineinander umformen lässt. Es ging mir darum, dass man durch die andere Denkweise Vereinfachungen der Problemstellung an sich erkennen kann, und dadurch dann massive Verbesserungen gegenüber naiveren Algorithmen gewinnen kann.

Ja, aber eben nur in der grauen Theorie. Die theoretische Informatik hat einen fatalen Hang bestimmte Dinge einfach unter den Tisch fallen zu lassen. Als Beispiel: Im Prinzip ist eine Matrizenmultiplikation ganz einfach, aber in der Realität sieht die Sache anders aus: Goto, van de Geijn Paper.

Bashar

Kann man diese Nebendiskussion nicht irgendwie abspalten? Der OP kann damit sicher nichts anfangen.

*john 0

@Bashar sagte in Rekursion - Hilfe bei der Umsetzung:

Kann man diese Nebendiskussion nicht irgendwie abspalten? Der OP kann damit sicher nichts anfangen.

Es ist keine Nebendiskussion, sondern ein wesentliches Lernziel, wenn es um die Problematik Schleifen und Rekursion geht. Es geht darum zu verstehen, dass man zwar theoretisch jede Schleife in eine Rekursion und umgekehrt umwandeln kann, aber das auch einen Preis hat. Man sieht das hier ganz schnell, wenn man keine trivialen Eingabewerte an die Funktionen übergibt.

#include <iostream>
#include <cstddef>
#include <cstdint>

//int f (const int i) {
//    return i;
//}

uint64_t f (const uint64_t) {
    return i;
}

uint64_t f_smart (const uint64_t end) {
    // Formel nach Gauß
    // return (end + 1) * (end / 2);
    return ((end + 1) * end) / 2; // Divison garantiert ohne Rest
}

uint64_t f_sum_recursion (const uint64_t start, const uint64_t end) {
    if (start == end) return f(start);

    // Der Compiler kann zuerst f(end) auswerten, oder er wertet zuerst f_sum_recursion aus.
    // Hier muss entweder der Rückgabe wert von f(end) oder end gespeichert werden, d.h. der
    // Speicherverbrauch ist in beiden Fällen gleich groß: (Rekursionstiefe - 1) * sizeof(uint64_t).
    return f(end) + f_sum_recursion(start, end - 1);
}

uint64_t f_sum_loop (const uint64_t start, const uint64_t end) {
    // f_sum_loop benöntigt exakt zwei uint64_t, den Rückgabewert und die Zählvariable für die Schleife.
    uint64_t r = 0;

    for (uint64_t i = start; i <= end; ++i) {
        r += f(i);
    }

    return r;
}

uint64_t f_sum_reduction (const uint64_t start, const uint64_t end) {
    uint64_t r = 0;
    #pragma omp parallel for reduction (+: r)
    for (uint64_t i = start; i <= end; ++i) {
        r += f(i);
    }

    return r;
}

int main () {
    std::cout << "fs = " << f_smart(100) << "\n";
    int r1 = f_sum_recursion(0, 100);
    int r2 = f_sum_loop(0, 100);
    int r3 = f_sum_reduction(0, 100);
    std::cout << "r1 = " << r1 << "\nr2 = " << r2 << "\nr3 = " << r3 << std::endl;

    std::cout << "fs = " << f_smart (1000000) << std::endl;
    std::cout << "fl = " << f_sum_loop (0, 1000000) << std::endl;
    std::cout << "fr = " << f_sum_recursion (0, 1000000) << std::endl;

    return EXIT_SUCCESS;
}

Bashar

@john-0 Und das ist jetzt eine Metadiskussion

*john 0

@Bashar sagte in Rekursion - Hilfe bei der Umsetzung:

@john-0 Und das ist jetzt eine Metadiskussion

Lieber Bashar,
es gab ganz am Anfang von SeppJ eine konstruktive und erschöpfende Antwort. Von mir gibt es nun eine Musterlösung. Wenn Du der Meinung bist, dass die Diskussion über die Vor- und Nachteile von Schleifen und Rekursion nicht zum Thema gehört und abgetrennt werden sollte, musst Du Dir gefallen lassen, dass man Dir widerspricht.

wob

@john-0 sagte in Rekursion - Hilfe bei der Umsetzung:

uint64_t f_sum_recursion (const uint64_t start, const uint64_t end) {
    if (start == end) return f(start);

    // Der Compiler kann zuerst f(end) auswerten, oder er wertet zuerst f_sum_recursion aus.
    // Hier muss entweder der Rückgabe wert von f(end) oder end gespeichert werden, d.h. der
    // Speicherverbrauch ist in beiden Fällen gleich groß: (Rekursionstiefe - 1) * sizeof(uint64_t).
    return f(end) + f_sum_recursion(start, end - 1);
}

Naja, so ganz korrekt ist das nicht. Sieht man auch, wenn man sich anguckt, wie der erzeugte Code aussieht - in diesem Beispiel stellt man nämlich fest, dass moderne Compiler hier den Rekursionsaufruf wegoptimieren und somit der Speicherverbrauch nicht von der Tiefe abhängig ist.

gcc 10.1 mit -O2 liefert:

f_sum_recursion(unsigned long, unsigned long):
        xor     eax, eax
        cmp     rdi, rsi
        je      .L15
.L14:
        movsx   rdx, esi
        sub     rsi, 1
        add     rax, rdx
        cmp     rsi, rdi
        jne     .L14
.L15:
        movsx   rdi, edi
        add     rax, rdi
        ret

Ich war erst kurz verwirrt wegen der 32->64-Bit-Fummelei, bis ich gesehen habe, dass dein f ja von int->int geht.

*john 0

@wob sagte in Rekursion - Hilfe bei der Umsetzung:

Naja, so ganz korrekt ist das nicht. Sieht man auch, wenn man sich anguckt, wie der erzeugte Code aussieht - in diesem Beispiel stellt man nämlich fest, dass moderne Compiler hier den Rekursionsaufruf wegoptimieren und somit der Speicherverbrauch nicht von der Tiefe abhängig ist.

Das Problem unterkomplexer Beispiele. Auf die Schnelle funktionierte es ohne Optimierung, sprich man kann sich nicht unbedingt darauf verlassen, dass der Compiler den Speicheraufwand weg optimieren kann.

wob

@john-0 sagte in Rekursion - Hilfe bei der Umsetzung:

uint64_t f_smart (const uint64_t end) {
// Formel nach Gauß
return (end + 1) * (end / 2);
}

Bevor das jemand abschreibt: Die Formel ist $\frac{n (n+1)}{2}$ . Bei dem Produkt n * (n+1) ist sichergestellt, dass einer der beiden Faktoren gerade ist und die Division aufgeht. Wenn du (end/2) einklammerst, funktioniert deine Formel funktioniert nur noch für gerade Zahlen. Dafür dann aber auch bei größeren Werten, da das Produkt später überläuft