Wozu ist rekursion nützlich ?
Übersicht
BlitzBasic Allgemein
|
sbrogBetreff: Wozu ist rekursion nützlich ? |
 Mo, Jun 07, 2004 22:39Antworten mit Zitat 
|
|---|---|---|
|
ich hab mal folgende rekursive funktion ausprobiert :
Code: [AUSKLAPPEN] Print multiply(3,4) WaitKey Function multiply(num,times) If times = 0 Then Return 0 Return num + multiply(num,times-1) End Function und festgestellt, dass in blitzbasic auch rekursion möglich ist. Leider weiß ich nicht , zu was rekursion gut sein soll. Kann mir mal jemand ein Beispiel zeigen, in dem rekursiv besser ist als iterativ ? [/code] |
||
René Meyer |
Mo, Jun 07, 2004 22:46 Antworten mit Zitat
|
|
|---|---|---|
|
Bei Bäumen, von denen Du nicht weißt, wie viele Äste sie haben und wie tief sie sind.
Nehmen wir an, Du willst alle Dateinamen auf der Festplatte auslesen. Dafür bietet sich Rekursion an. |
||
| www.blitzbasic.de | Das Buch zu Blitz Basic: www.schreibfabrik.de/txt/bbb | ||
Dreamora |
Mo, Jun 07, 2004 23:30 Antworten mit Zitat
|
|
|---|---|---|
| nen anderer ort wo du ohne rekursion gleich vorweg wieder einpacken kannst ist auch Pathfinding und alles was in die richtung geht, da das normalerweise auf Backtracking basiert, was wiederum auf rekursion basiert | ||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
|
joKe |
Mo, Jun 07, 2004 23:55 Antworten mit Zitat
|
|---|---|---|
|
Rekusrion ist auch toll um sich Fakultät Funktionen zu schreiebn oder exponentielle wachstümer wie Hasenvermehrung oder das berühmte Apfelmännchen
alles mit Rekursion gemacht aber vorsicht ! schlecht programmierte oder "zu tiefe" rekusrion bringt selbst nen 3000 Mhz Pc in den Keller der Rechenleistung |
||
|
Projekt: Pollux Renegades Coop
[Maschine: Intel DualCore2 2x 3Ghz | 4096 DRR2 | GeForce GTX 260 Ultra] |
||
Dreamora |
Di, Jun 08, 2004 0:37 Antworten mit Zitat
|
|
|---|---|---|
| nebenher sind rekursionen übrigens der grund für die bei Blitz3D lern zumindest noch unbekannte "stack overflow" krankheit | ||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
furbolg |
Di, Jun 08, 2004 15:08 Antworten mit Zitat
|
|
|---|---|---|
|
stimmt, das ist aber bei allen Programmen oder PSprachen so. Das liegt an dem 1 MB großen Stack den jedes Programm von Windows kriegt. Darin wird der Aufruf gespeichert mit Parametern. Also wenn man ne Funktion 1 Milliarde mal aufruft is die wahrscheinlichkeit groß das der Stack verbraucht ist -> error ^^
Deswegen, rekursion hat auch tücken 
|
||
Dreamora |
Di, Jun 08, 2004 15:11 Antworten mit Zitat
|
|
|---|---|---|
| hmm 1mb ... bin mir jetzt net sicher aber wurde der in XP net erhöht? | ||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
MasterK |
Di, Jun 08, 2004 18:00 Antworten mit Zitat
|
|
|---|---|---|
|
furbolg hat Folgendes geschrieben: stimmt, das ist aber bei allen Programmen oder PSprachen so.
nicht jede sprache (bzw compiler/interpreter) unterstützt rekursion furbolg hat Folgendes geschrieben: Das liegt an dem 1 MB großen Stack den jedes Programm von Windows kriegt. Darin wird der Aufruf gespeichert mit Parametern. Also wenn man ne Funktion 1 Milliarde mal aufruft is die wahrscheinlichkeit groß das der Stack verbraucht ist -> error ^^
naja, da bekommst du nichtmal ne million aufrufe hin 
aber weist windows wirklich ne konstante stackgrösse zu? eigentlich sollte die doch (halb)dynamisch sein. bzw ein stack ist ja an sich erstmal immer dynamisch. dass der verfügbare speicher irgendwann verbraucht ist ist klar, aber jedem prozess pauschal 1mb zuweisen? wäre etwas übertrieben. |
||
dubitat |
Di, Jun 08, 2004 18:01 Antworten mit Zitat
|
|
|---|---|---|
| dann sollte man also mit so wenig funktionen wie möglich coden? ich meine doch eher das gegenteil gehört zu haben! | ||
| Erare humanum est - Irren ist Menschlich | ||
Edlothiol |
Di, Jun 08, 2004 18:03 Antworten mit Zitat
|
|
|---|---|---|
|
Was auch gut mit Rekursion möglich ist, sind Parser. Top - Down Parser basieren eigentlich immer auf Rekursion (die Methode heißt auf Deutsch ja auch Rekursiver Abstieg). Es gibt dann auch noch Bottom - Up Parser, die arbeiten soviel ich weiß mit Stacks.
Rekursion lässt sich durch Benutzung eines eigenen Stacks eigentlich immer verhindern. Nur kannst du da genauso einen Stack Overflow kriegen 
Zitat: dann sollte man also mit so wenig funktionen wie möglich coden? Was soll das heißen? Es geht darum, wie verschachtelt die Aufrufe werden können.
|
||
|
regaa |
Di, Jun 08, 2004 19:26 Antworten mit Zitat
|
|---|---|---|
| Also ab und an kackt bei mir bb in zusammenhang mit rekursionen ab. Ich weiß einfach nicht wodran es liegt. Also wenn sich eine rekursive Funktion in einer Normalen befindet, geht bb an dieser stelle so raus, als ob da ein end befehl wäre. Ich hab jetzt aber kein Beispiel, es passiert auch nicht immer, aber oft in zusammenhang mit rekursiven Funktionen. | ||
|
UltraMixer Professional 3 - Download
QB,HTML,CSS,JS,PHP,SQL,>>B2D,B3D,BP,BlitzMax,C,C++,Java,C#,VB6 , C#, VB.Net |
||
Edlothiol |
Di, Jun 08, 2004 19:56 Antworten mit Zitat
|
|
|---|---|---|
| Ich glaube, BB beendet sofort ohne Meldung, wenns nen Stack Overflow gibt. Bin mir aber nicht sicher. | ||
|
TheShadowModerator |
Di, Jun 08, 2004 21:03 Antworten mit Zitat
|
|---|---|---|
|
Habe Pathfinding und Verzeichnis auslesen absichtlich ohne Rekursion gemacht - weil "flachere" Programme sind meist einfacher und schneller... Da verwaltet man die Daten lieber in sogenannten To-Do-Listen.
Bei Schach-KI eignet sich Rekursion dagegen perfekt - dort müssen mögliche Schritte gefunden werden und dann jeden Schritt "nachgehen" - bei 5-facher-Rekursion können locker bis zu 400.000 mögliche Schritte geprüft werden... Habe mich auch gewundert - bei 10-facher Rekursion ist mein Prog aufgrund von Millionen (oder Milliarden?) von Berechnungen "hängen" geblieben
|
||
| AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2 | ||
|
|
regaa |
Mi, Jun 09, 2004 11:34 Antworten mit Zitat
|
|---|---|---|
|
Edlothiol hat Folgendes geschrieben: Ich glaube, BB beendet sofort ohne Meldung, wenns nen Stack Overflow gibt. Bin mir aber nicht sicher.
Sieht zumindest immer so aus. |
||
|
UltraMixer Professional 3 - Download
QB,HTML,CSS,JS,PHP,SQL,>>B2D,B3D,BP,BlitzMax,C,C++,Java,C#,VB6 , C#, VB.Net |
||
Dreamora |
Mi, Jun 09, 2004 13:49 Antworten mit Zitat
|
|
|---|---|---|
| weiss net obs im normalen modi is oder im debug, aber in einem von beiden quittiert er mit stack overflow messagebox | ||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
|
Blatolo |
Mi, Jun 09, 2004 14:08 Antworten mit Zitat
|
|---|---|---|
|
bei debug wird ohne fehlermeldung beendet und ohne debug wird "stack overflow" angezeigt.
Allerdings hatte ich den Fehler letztens auf einem rechner. Bei mir läuft das Programm ohne Probleme und es benutzt keine Rekursion. Außerdem benutzt mein pathfinding rekursion. Früher lief es einwandfrei nur seit ein paar änderungen kommt immer stack overflow. |
||
Dreamora |
Mi, Jun 09, 2004 14:10 Antworten mit Zitat
|
|
|---|---|---|
| ich tippe ma drauf, dass durch die "paar änderungen" die suchtiefe für die rekursion drastisch angestiegen ist. | ||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
|
|
Blatolo |
Mi, Jun 09, 2004 14:46 Antworten mit Zitat
|
|---|---|---|
|
Die änderungen waren wirklich nur geringfügig.
Außerdem beeinflussten sie nicht die Rekursion sondern optimierten jediglich eine Stelle des codes die ich sehr umständlich gecodet hatte. edit: läuft wieder
|
||
Übersicht
BlitzBasic Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group