c++.de :: Was ist ein rekursive Funktion (oder so ähnlich)?

Speddy Conzales Mitglied 23:10:00 04.01.2001 Titel:

Hi!
Ich hoffemal, daß ich hier das richtig Forum erwischt habe.
Meine Frage:
Was ist ein rekursive Funktion/Procedure?
Könntet ihr mir dazu einen Quelltext (C) posten oder erklären was das ist?
Danke im voraus [img]http://www.c-plusplus.de/ubb/ubb/smile.gif[/img].

Bahal Mitglied 23:27:00 04.01.2001 Titel:

Eine rekursive Funktion ist eine Funktion die sich, in ihrem Verlauf selbst wieder
aufruft (mit anderen Werten).
Bsp:

void funktion (...)
{
... blabla...
funtion(...);
}

Ciao
Bahal

Fux Mitglied 01:05:00 05.01.2001 Titel:

Was Bahal gesagt hat ist richtig. Ich will dir nur noch einen Link auf Volkard Kurs mitgeben. Dort hast du auch gleich den Klassiker - die Fakultät. http://www.c-plus-plus.de/rekursion.html
CU

[Diese Nachricht wurde von Fux am 05-01-2001 editiert.]

Seppel Mitglied 17:56:00 05.01.2001 Titel:

Hallo,

wirklich sinnvoll ist der rekursive Aufruf aber nur bei "Baeumen". So z.B. bei Iterationen (Fakultaet kriegt man ja auch anders hin).
Stell dir vor, du willst einen Baum malen der folgender massen aussieht:

Stamm... dann kommt eine Verzweigung -> 2 Aeste...
an jedem Ast wieder eine Verzweigung -> wieder pro Ast 2 neue Aeste ... usw.

Willst du jetzt einen solchen Baum mit bspw. 5 Iterationen/Stufen malen, so geht das nur sehr schlecht hintereinander zu machen (versuche es einmal... wo faengt man an?).
Genau an dieser Stelle hilft dir die Rekursion:
1. du schreibst einfach eine Funktion, die dir an einen "Grundast" eine Verzweigung und 2 Aeste malen kann: aeste_malen(Grundast);
2. dann rufst sich dieselbe Fkt. selbst fuer die beiden neuen Unteraeste auf.
3. Gestartet wird die Rekursion mit dem Stamm
4. Abbruchbedingung nicht vergessen!
(bspw. die Astdicke, wenn sie jedesmal bei einer Verzweigung veringert wird)

Pseudocode:

void aeste_malen(Grundast)
{
-1.Zweig an den Grundast anmalen
-2.Zweig an den Grundast anmalen

wenn Abbruchbedingung nicht erfuellt:
{
-aeste_malen(1.Zweig);
-aeste_malen(2.Zweig);
}
}

void main()
{
...
aeste_malen(Stamm);
...
}

(ich hoffe das war jetzt irgendwie verstaendlich [img]http://www.c-plusplus.de/ubb/ubb/wink.gif[/img] ?)

Eine richtige Anwendung ist aber nicht das malen von Baeumen sondern z.B. Fraktale in verschiedenen Iterationsstufen...

Wenn du daran Interesse hast, schreib' einfach noch einmal...

Tschuess, Seppel.

Knollo Mitglied 01:38:00 06.01.2001 Titel:

Tach
Ne andere cool Anwendung von solch Funktionen ist eine Explosion im Kultspiel Bomberman. Wenn eine Bombe explodiert lößt sie in der Nähe befindliche Bomben mit aus. Dazu muss die Umgebung abgecheckt werden und das von jeder ausgelösten Bombe aus. Ohne Rekursion to mein mind unmöglich.

------------------
www.knollo.purespace.de

Unregistrierter

Zitat:
Original erstellt von Knollo:
Wenn eine Bombe explodiert lößt sie in der Nähe befindliche Bomben mit aus. Dazu muss die Umgebung abgecheckt werden und das von jeder ausgelösten Bombe aus. Ohne Rekursion to mein mind unmöglich.

DAS ist in der Tat mal ein sehr gutes Beispiel für eine Rekursion. Danke für den Hinweis, das werde ich mir merken.

Dennoch eine Anmerkung: jede rekursive Funktion läßt sich so umschreiben, daß man das Problem rein iterativ löst. Meistens ist dazu eine Hilfsdatenstruktur (Liste, Stack) notwendig. Man kann sowohl die Fakultät als auch einen Baumdurchlauf durchaus nicht-rekursiv programmieren. Allerdings ist die rekursive Lösung oftmals kürzer und intuitiver verständlich.

------------------
Viele Grüße

Marc++us

Besucht die C/C++-Ecke
http://www.c-plusplus.de

Speddy Conzales Mitglied 14:04:00 07.01.2001 Titel:

Ein ganz großes Dankeschön an alle [img]http://www.c-plusplus.de/ubb/ubb/smile.gif[/img].
Ihr habt mir richtig gut geholfen [img]http://www.c-plusplus.de/ubb/ubb/smile.gif[/img].
THX & Thumps up für dieses Board...