rekursive funktion als while-loop |
14.12.2006, 10:01 | Auf diesen Beitrag antworten » | |||||
asm_user | rekursive funktion als while-loop hi, wie kann ich folgende rekursive funktion mittels einer while-schleife lösen:
danke im voraus. |
|||||
|
||||||
14.12.2006, 10:51 | Auf diesen Beitrag antworten » | |||||
Friedrich | erstens, ist die Funktion fehlerhaft, da sie ins unendliche rekursiert, falls man sie mit p(1); aufruft!! Nachdem du das abgefangen hast... musst du dir nun klarmachen, was passiert, wenn man sie mit zB p(4) oder einer anderen Zahl >= 2 aufruft |
|||||
14.12.2006, 12:29 | Auf diesen Beitrag antworten » | |||||
asm_user | das ist eine frage von einem probe test ... die zu beantworten ist .. |
|||||
14.12.2006, 12:32 | Auf diesen Beitrag antworten » | |||||
David1979 | Hallo asm_user, noch als kleinen Zusatztip: Oft kann man den Verlauf der Funktion relativ einfach abschätzen, bzw. auch feststellen, wenn man die rekursive Funktion mit (kleinen) Parametern füttert und sich den Verlauf ansieht. Schwieriger wird es allerdings oft, wenn man für die linearisierte Fassung die (Abbruch-)Bedingungen finden will. Hierzu noch folgendes: Oft kann man das Problem so lösen, dass man sich in der Bedingungsfolge von unten nach oben arbeitet, bzw von dem Term der den rekursiven Aufruf enthält zu den anderen, insbesondere dann, wenn zu dem Ergebnis der Rekursionsfolge noch die Werte hinzugerechnet werden müssen, die keinen rekursiven Term enthalten. Jetzt bleibt nur noch die Frage, wie man den rekursiven Term auflöst. Hier bietet sich eigentlich generell die Methode der Invariante an. Dabei betrachtet man immer einen Rekursionsschritt und beschreibt mit einer Invariante und einer Nachbedingung, die Zustände während und nach eines Iterationsschrittes. Mit einer Vorbedingung legt man den Zustand fest, der vor dem Schleifen durchlauf gegeben sein muss. Hält man sich an diese Bedingungen, dann dürfte eigentlich nicht viel schief gehen. An deinem Beispiel mit nem Pseudocodeschnipsel verdeutlicht:
Ich hoffe, dass hilft auch bei zukünftigen Aufgaben bzgl. Linearisierung einer Rekursion. // EDIT: Übrigens: Wenn du mal nachprüfst, was Friedrich über den Fehler gesagt hat, wirst du schnell merken, dass es da tatsächlich einen Fehler gibt! Es sei denn du hast die Funktion falsch gepostet. Also ERST prüfen, DANN antworten. |
|||||
Anzeige | ||||||
|
||||||
14.12.2006, 15:33 | Auf diesen Beitrag antworten » | |||||
ed209 | Hier bin ich auch durchaus der Ansicht daß man das ganze mit ein bisschen Mathematik auch ohne Schleife oder Rekursion in konstanter Zeit lösen kann Gruß, ED209 |
|||||
20.01.2007, 19:05 | Auf diesen Beitrag antworten » | |||||
donvito | Ich dachte immer, dass Rekursion immer ohne Schleifen funktioniert, oder liege ich da falsch? Rekursion bedeutet doch, dass eine Methode sich selbst immer wieder aufruft, bis sie irgendwo ein Ende findet. Dann brauche ich keine Schleifen... |
|||||
20.01.2007, 23:47 | Auf diesen Beitrag antworten » | |||||
Crotaphytus | Aber es geht hier darum, die Rekursion zu entfernen... |
|