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:
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
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