Rekursion

_matze schrieb:

std::cout "Alles klar!";

da fehlt der links-shift.

_matze

+fricky schrieb:

_matze schrieb:

std::cout "Alles klar!";

da fehlt der links-shift.

Klugsch...

Bashar ich hab die Funktionen schon vertstanden.

Was jedoch nicht ganz in meinen Kopf reingeht ist, wie sich die Funktion selber aufruft und gleichzeitig ein Rückgabewert sein kann.

Thx für die bisherigen Antworten.

_matze

Der Hans schrieb:

Bashar ich hab die Funktionen schon vertstanden.

Was jedoch nicht ganz in meinen Kopf reingeht ist, wie sich die Funktion selber aufruft und gleichzeitig ein Rückgabewert sein kann.

Das ist schon ein kleiner Widerspruch, aber na ja...

Deine Funktion hat einen Rückgabewert. D.h., immer wenn sie aufgerufen wird, gibt sie auch einen Wert zurück. Wenn sie sich nun selbst wieder aufruft (was bedeutet, dass da eine zweite Funktion selben Typs, eine Kopie der Funktion mit eigenen Variablen, läuft, wenn man so will), dann ändert das nichts daran, dass eine Rückgabe stattfindet. Auch wenn der Rückgabe-Wert in der "ersten" Funktion verarbeitet wird. Klar? Oder zumindest klarer?

Jo klarer
Betrachten wir mal die folgende Zeile (bei n = 3):

return n * fak_rekursiv(n - 1);

Statt fak_rekursiv(n - 1) schreiben wir mal fak_rekursiv(2).
Das 3 - 1 = 2 ist, ist mir klar. Aber wieso bekommt die Funktion den Wert 2 damit man mit dem rechnen kann..?

_matze

Na du willst ja erreichen, dass bei Fakultaet(5) 5*4*3*2*1 gerechnet wird. Also rufst du beim ersten Mal n*Fakultaet(n-1) auf, also 5*Fakultaet(4). Fakultaet(4) ist 4*Fakultaet(3) usw. Am besten du schreibst dir mal Schritt für Schritt jeden Aufruf und das Ergebnis auf ein Blatt Papier, dann sollte es klar sein.

Bashar

Der Hans schrieb:

Bashar ich hab die Funktionen schon vertstanden.

Was jedoch nicht ganz in meinen Kopf reingeht ist, wie sich die Funktion selber aufruft und gleichzeitig ein Rückgabewert sein kann.

Würdest du die fak_rekursiv-Funktion verstehen, wenn da statt fak_rekursiv ein Aufruf einer anderen Funktion (z.B. fak_iterativ) stehen würde? Was du geschrieben hast, liest sich eher so, als hättest du mit dem grundsätzlichen Konzept von Funktionen und Rückgabewerten Probleme.

Ja das ist mir schon klar..
Aber wieso ist:

fak_rekursiv(5)
=
5

?

Bashar

Ist es doch gar nicht.

Bashar schrieb:

Ist es doch gar nicht.

Jetzt versteh ich gar nichts mehr..
Und wie kommt man dann zum ergebnis?

Bashar schrieb:

Der Hans schrieb:

Bashar ich hab die Funktionen schon vertstanden.

Was jedoch nicht ganz in meinen Kopf reingeht ist, wie sich die Funktion selber aufruft und gleichzeitig ein Rückgabewert sein kann.

Würdest du die fak_rekursiv-Funktion verstehen, wenn da statt fak_rekursiv ein Aufruf einer anderen Funktion (z.B. fak_iterativ) stehen würde? Was du geschrieben hast, liest sich eher so, als hättest du mit dem grundsätzlichen Konzept von Funktionen und Rückgabewerten Probleme.

Die Funktionen sind mir klar..
Unterprogramm starten, den neuen Wert berechnen und zurückgeben.

_matze

Ja, und Funktionen bzw. deren Rückgabewerte kannst du direkt in Ausdrücken verwenden. War das vielleicht noch nicht ganz klar?

int i=1+quadrat(2);  //i wird 1 + die Rückgabe von quadrat (also wahrscheinlich 4) zugewiesen

Ich bin gerade am verzweifeln.

In der Hoffnung das ich es verstehen werde, hab ich mir ein kleines Bild gebastelt. So wie ich das verstanden habe, werden die Funktionen ineinander aufgerufen.

http://img264.imageshack.us/img264/6918/rekursion.gif

Bei "return 1;" angelangt wird immer der Rückgabewert der vorherigen Funktion gegeben oder?

_matze

Der Hans schrieb:

Ich bin gerade am verzweifeln.

Ganz ruhig, am Anfang hat man es immer schwer, aber das wird schon.

Der Hans schrieb:

In der Hoffnung das ich es verstehen werde, hab ich mir ein kleines Bild gebastelt. So wie ich das verstanden habe, werden die Funktionen ineinander aufgerufen.

Sieht aus, als hättest du es verstanden.

_matze schrieb:

Der Hans schrieb:

Ich bin gerade am verzweifeln.

Ganz ruhig, am Anfang hat man es immer schwer, aber das wird schon.

Der Hans schrieb:

In der Hoffnung das ich es verstehen werde, hab ich mir ein kleines Bild gebastelt. So wie ich das verstanden habe, werden die Funktionen ineinander aufgerufen.

Sieht aus, als hättest du es verstanden.

Muahaha wie geil
Derzeit kann ich mir aber schwer vorstellen, dass ich solche Funktionen schreibe.. Erst mal drüber schlafen :p

Vielleicht könntet ihr mir ja eine kleine Aufgabe stellen

_matze

Der Hans schrieb:

Derzeit kann ich mir aber schwer vorstellen, dass ich solche Funktionen schreibe.. Erst mal drüber schlafen :p

Vielleicht könntet ihr mir ja eine kleine Aufgabe stellen

Ich denke, eine typische Aufgabe für Rekursion ist das Wandern durch einen Verzeichnis-Baum. Du weißt nie, wieviele Unterverzeichnisse es gibt, daher bietet Rekursion sich an. Du könntest eine Funktion schreiben, die alle Dateien in einem Verzeichnis inklusive Unterverzeichnissen ausgibt (also quasi ein eingeschränkter DIR-Befehl). Das habe ich damals auch mal gemacht. Ich habe früher aus Spaß mehrere DOS-Befehle nachgebastelt, z.B. auch den TREE-Befehl, der die Verzeichnisstruktur "pseudo-grafisch" abbildet (ich hab ihn aber aufgepeppt mit Farben und zusätzlichen Infos ).

Bashar

* Türme von Hanoi
* alle Permutationen eines Arrays ausgeben (ohne next_permutation)

Das sind auch Probleme, bei denen die iterative Lösung IMO schwieriger ist.

Der Hans schrieb:

Vielleicht könntet ihr mir ja eine kleine Aufgabe stellen

auch noch: mach 'ne rekursive funktion, die zahlen in verschiedenen zahlensystemen ausgeben kann. ohne führende nullen natürlich.

void print_number (unsigned number, unsigned base)
{
  // ?
}

_matze schrieb:

Ich denke, eine typische Aufgabe für Rekursion ist das Wandern durch einen Verzeichnis-Baum. Du weißt nie, wieviele Unterverzeichnisse es gibt, daher bietet Rekursion sich an. Du könntest eine Funktion schreiben, die alle Dateien in einem Verzeichnis inklusive Unterverzeichnissen ausgibt (also quasi ein eingeschränkter DIR-Befehl). Das habe ich damals auch mal gemacht. Ich habe früher aus Spaß mehrere DOS-Befehle nachgebastelt, z.B. auch den TREE-Befehl, der die Verzeichnisstruktur "pseudo-grafisch" abbildet (ich hab ihn aber aufgepeppt mit Farben und zusätzlichen Infos ).

Gibts für den Umgang mit Verzeichnissen eine gute Beschreibung/Tutorial? (außer das auf Linux..)

Ich mach mir gerade ein Tool, dass alle Dateien in einem Verzeichnis nach einem Wort durchsuchen sollte, und diese Dateien (in denen das Wort enthalten ist) in einen neuen Ordner verschiebt.
Bis jetzt hab ich es geschafft, eine einzelne Datei zu durchsuchen, jedoch hab ich keine Ahnung wie man das bei allen Dateien schafft und auch deren Namen bekommt.
Ich hab den Namen der Datei im Code eingegeben.

Gruß
Der Hans

hartmut1164

Um was es bei einer Rekurison geht ist eine Funktion auf N in eine andere Form umzuwandeln. Bleiben wir bei der Fac:

n
n! := [e]Pi[/e]n = 1 * 2 * 3 ... (n - 1) * n = f (n)
      i=1

man kann daraus eine Funktion g (n) machen:

n!  := g (n (g (n-1)) [e]Lambda[/e] 
g (1) := 1;

Am Rande:
Die Fakultaet ist zwar immer das Schulbeispiel fuer eine Rekursion, aber eigentlich ein sehr schlechtes Beispiel fuer die Praxis, weil selbst bei Datentyp double 100! die Grenzen schon sprengt; man ist hier besser mit einer if-else oder case-Struktur bedient.