Wann Rekursion anwenden? (z.B. Bubblesort)

FireFlow

Erfahrenes Mitglied
Hallo!

Irgendwie kann man jede Funktion die eine Schleife hat rekursiv erstellen. Wann macht es Sinn eine Funktion rekursiv zu erstellen? Ist mir gerade beim Bubblesort aufgefallen...

Beispiel:

Code:
//---------------------------------------------------------------------------
// Bubble Sort: Iterative Funktion
// void bubblesort<T>(T*, unsigned int const&);
//---------------------------------------------------------------------------

template <class T>
void bubblesort(T* array, unsigned int const& size)
{
    // Abbruchbedingung falls schon fertig sortiert
    bool changed;
    // Schleife 1
    for(int i=1; i<size; ++i)
    {
        // Noch nichts geändert
        changed = false;
        // Schleife 2
        for(int j=0; j<size-i; ++j)
        {
            // Vergleich
            if(array[j] > array[j+1])
            {
                // Tausch
                changed = true;
                swap(array[j], array[j+1]);
            }
        }
        // Abbrechen wenn nichts geändert wurde
        if(!changed) break;
    }
}

Code:
//---------------------------------------------------------------------------
// Bubble Sort: Rekursive Funktion
// void bubblesort_r<T>(T*, unsigned int const&);
//---------------------------------------------------------------------------
template<class T>
void bubblesort_r(T* array, unsigned int const& size)
{
    // Abbruchbedingung falls schon fertig sortiert
    bool changed = false;
    // Schleife (=Schleife 2 aus iterativer Funktion)
    for(int j=0; j<size-1; ++j)
    {
        // Vergleich
        if(array[j] > array[j+1])
        {
            // Tausch
            changed = true;
            swap(array[j], array[j+1]);
        }
    }
    // Abbrechen wenn nichts geändert wurde oder letzter Durchgang
    if(!changed || size==1) return;
    // Ansoten rekursion
    bubblesort_r(array, size-1);
}

Wenn ich das richtig verstehe läuft eine rekursive Funktion meist schneller braucht aber mehr Speicher. Das sagt mir aber immer noch nicht was besser ist, bzw ob es überhaupt einen Unterschied macht.

Gruss FireFlow
 
Eine rekursive Funktion läuft nicht unbedingt (meist eher nicht) schneller als ihr iteratives Äquivalent, da durch die ständigen Funktionsaufrufe Zeit verloren geht.

Die interative Lösung ist jedoch meist länger, was den Quellcode und das Kompilat angeht.

In der Regel haben rekursive Funktionen also wenig bis keine Vorteile gegenüber einer iterativen Lösung, wenn man es zur Laufzeit betrachtet. Allerdings ist es so, dass sich viele Algorithmen rekursiv leichter beschreiben lassen und daher der Programmieraufwand geringer ausfällt (sofern man mit dem Prinzip der Rekursion vertraut ist). Bei manchen (funktionalen) Programmiersprachen ist die Rekursion deswegen sogar elementarer Bestandteil (z.B. LISP, Scheme).
 
Ist eine rekursive Lösung also nur sinnvoll wenn man sich dadurch Programmieraufwand spart?

Ich hab im Internet gefunden dass Compiler anderer Sprachen eine Funktion haben die rekursive Funkionen automatisch umwandelt in eine iterative Variante. Gibts solche Optimierungen auch für C/C++ Compiler? In meinem BCB hab ich nichts gefunden und MSVC hab ich grade nicht zur Hand.
 
FireFlow hat gesagt.:
Ist eine rekursive Lösung also nur sinnvoll wenn man sich dadurch Programmieraufwand spart?
Es geht nicht nur um den Aufwand, sondern auch um die Les- und Wartbarkeit des Quellcodes. Die sind in bestimmten Fällen bei Anwendung von Rekursion eher gewährleistet.

Ich hab im Internet gefunden dass Compiler anderer Sprachen eine Funktion haben die rekursive Funkionen automatisch umwandelt in eine iterative Variante. Gibts solche Optimierungen auch für C/C++ Compiler? In meinem BCB hab ich nichts gefunden und MSVC hab ich grade nicht zur Hand.
Für andere Sprachen ist das sicher möglich, bei C/C++ stell ich mir das aber etwas kompliziert vor. Wo hast du denn diese Information gefunden?
 
Ja, LISP, dachte ich's mir doch :) Das liegt aber daran, dass LISP eine funktionale Programmiersprache und von daher voll auf Funktionen abgestimmt ist.

C ist im Vergleich viel maschinennäher. Eine Funktion wird hier nicht primär als logische Programmeinheit gesehen, die andere Funktionen oder sich selbst aufrufen kann, sondern als Block von Anweisungen im Speicher an einer bestimmten Adresse, auf die bei Bedarf während der Programmausführung gesprungen wird.

Von daher wäre es ein ziemlicher Aufwand, den C-Compiler einen rekursiven in eine iterativen Algorithmus ummünzen zu lassen. Der Compiler an sich "weiß nicht", was Rekursion ist. Er übersetzt nur in Maschinensprache.
 
Zurück