rekursive funktion als while-loop

Neue Frage »

Auf diesen Beitrag antworten »
asm_user rekursive funktion als while-loop

hi,

wie kann ich folgende rekursive funktion mittels einer while-schleife lösen:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
public static int p(int n)
{
  if (n == 3)
	return 1;
  else if (n == 2)
	return 0;
  else
	return (n + (n+1) + p(n-1));
}

danke im voraus.
 
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
Auf diesen Beitrag antworten »
asm_user

das ist eine frage von einem probe test ... die zu beantworten ist ..
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:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
function p(n:Integer):Integer {

    // Precondition: Unsere Variable result enthält zu Beginn der Iteration 
    // den Wert 0 und n >= 2. (Der Fehler, den Friedrich beschrieben hat, 
    // fangen wir hier nicht ab. In dem Fall wird 0 zurückgegeben). Das ist 
    // die Ausgangssituation vor der Iteration.
    result = 0;     

    while (n > 3) {
         // Invariante: Sagt aus, was zum Zeitpunkt eines Iterationsschrittes
         // als Bedingung in der Schleife gegeben sein muss. Hier ist die
         // Bedingung lediglich, dass n > 3 gegeben sein muss. Die Bedingung 
         // n > 3 kommt daher, weil wir uns vom rekursiven Term zu den
         // anderen hangeln.

         ...
    }
    // Postcondition: result = result + 2n+1 (zusammengefasst) und n = n-1
    // Die Nachbedingung, beschreibt den Zustand nach einem Iterations-
    // schritt.

    // Jetzt kümmern wir uns um die anderen und restlichen Fälle:
    // Die stärkere Bedingung zuerst.
    if (n == 3) {
        result = result + 1;
    }

    // Da wir am Anfang result schon mit 0 initialisiert haben, haben wir den
    // Fall, dass n==2 ist bereits abgedeckt. Auch wenn wir in der Schleife
    // gewesen sind, dann wird ja nichts dazuaddiert. Also einfach result
    // zurückgeben.
    return result;
}


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. smile
 
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 smile

Gruß,
ED209
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...
Auf diesen Beitrag antworten »
Crotaphytus

Aber es geht hier darum, die Rekursion zu entfernen...
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »