Rekursionsaufgabe

[Biene88]

Hallo zusammen!

Ich bin neu in diesem Forum und absoluter Java-Anfänger.
Ich studiere im 3. Semester Communication and Multimediadesign und da gehört auch ein Semester Computertechnik zu, in dem wir grob in die Informatik eingewiesen werden. Natürlich lässt sich Programmierung da nicht vermeiden.

Ich möchte hier jetzt zwei Aufgaben vorstellen, eine davon konnte ich lösen, bei der anderen habe ich Schwierigkeiten.

Vielleicht sollte ich noch dazu sagen, das ich Computertechnik eigentlich im ersten Semester hatte und dort C# beigebracht bekam, da ich durch die Prüfung gefallen bin es jetzt wiederholt habe und uns eigentlich Java beigebracht werden sollte, allerdings konnte der Prof das selbst nicht so, er kennt sich auch besser in C aus -.-. Deshalb habe ich bei Java leider nicht so den Durchblick.

Ich fang einfach mal an:

1. Aufgabe:

Was berechnet folgende Funktion? Erstellen Sie eine Tabelle in der Sie für die Zahlen von n=0 bis 10 das jeweilige Ergebnis und die Anzahl der Aufrufe der Funktion eintragen.

[JAVA=42]int A(int n)
{
if(n < 2)
return n;
else
return A(n - 1) + A(n - 2);
}[/code]

Mit dieser Aufgabe hatte ich eigentlich keine Probleme. ich fange an und setze in

int A(int n)einfügen

n=0. Dann steht in der nächsten Zeile

if(0 < 2)

und somit gebe ich die Null aus. Für n=1 funktioniert das dann auch noch. Dann setze ich n=2 und springe zum ersten Mal in die Zeile

return A(n - 1) + A(n - 2)

. Setze ich n=2 dort an erhalte ich den Wert 1 für die erste Klammer und den Wert 0 für die zweite Klammer und komme mit der Addition auf den Wert 1, den ich wiederrum ausgebe. Somit haben wir schon "0,1,1" ausgegeben.

Bei n=3 habe ich mich zum ersten Mal verhaspelt, weil ich direkt die Endergebnisse der Klammern (2, 1) addiert habe, ohne sie oben wieder aufzurufen. Das sollte natürlich nicht passieren, aber irgendwann habe ich es rausgefunden und für n=3 die Ausgabe 2 erhalten.

Damit zeichnete sich dann so langsam ab, das diese Rekursion die Fibonacci-Folge ausgibt.
Schwierig ist im Nachhinein hierbei nur, die Aufrufe zu zählen und aufzuschreiben. Außer zählen habe ich da noch keine bessere Lösung für gefunden.


Nun die 2. Aufgabe, die mir Schwierigkeiten bereitet:

Was berechnet folgendes Programm? Erstellen Sie eine Variablentabelle, in der Sie die Werte der Variablen für jeden Rekursionsdurchlauf eintrage.

[JAVA=42]public static void main(String args[]) {
int x = f1(10);
}
public static int f1(int i) {
if (i==0) {
return i;
}
int x = i+f1(--i);
return x;
}[/code]

Die Aufgabenstellung ist dieselbe wie oben, nur das ich hier die Aufrufe nicht zählen brauche.
Trotzdem schaffe ich es nicht, sie zu lösen.
Mein Problem sind hier zwei unbekannte Variablen, nämlich x und i (und nicht wie oben nur n).
Ich fange damit an und setze i=0.
Somit bliebe die erste Zeile

int x = f1(10)

noch unberührt.
Mit dem nächsten Aufruf würde ich dann 0 ausgeben.

Nun setze ich i=1.
Damit rutsche ich in die nächste Zeile

int x = i+f1(--i)

und bekäme 1+10 (-1). Damit wären wir bei 10 und würden 10 ausgeben.
Das macht aber keinen Sinn, weil für jedes weitere i die Lösung trotzdem 10 wäre...

Ich vermute, das ich mich hier ziemlich blöd anstelle und wenn man es mir einmal erklärt ich es dann auch lösen kann. Aber solange der Groschen nicht fällt und ich weiß, wie man so ein Programm liest, um es zu lösen, nützt mir das in der Klausur nur wenig.

Aber ich hoffe, das mir hier jemand auf die Sprünge helfen kann und mir zeigt, was ich falsch mache

LG
Biene88

 

[SlaterB]

mit welcher Begründung kommst du von [c]int x = i+f1(--i)[/c] auf 1+10 (-1)?
woher nimmst du die 10, aus dermain-Methode?

hier sollst du sowieso nicht von i=0 ausgehen + verschiedenes einsetzen, sondern den einen konkreten Aufruf verfolgen,
als erstes wird die Methode mit i== 10 aufgerufen, also 10 irgendwo als i eintragen,
das x für diese Stufe kann man noch nicht kennen, weil das vom nächsten Aufruf für i=9 abhängt,
also mach die eine Tabelle für alle i runter bis 0, dannn kannst du endlich erste x-e ausrechnen und nach und nach alles auffüllen

vergleichbar mit der Verfolgung eines Aufrufes int A(int n) für n = 6, da hättest du ja auch ne Menge zu tun

 

[M_Schaffrath]

Nun setze ich i=1.
Damit rutsche ich in die nächste Zeile

int x = i+f1(--i)

und bekäme 1+10 (-1). Damit wären wir bei 10 und würden 10 ausgeben.

Nein, da hast du irgendwie einen Denkfehler drin.

i

hat den Wert 1.

--i

ist der um 1 verringerte Wert von

i

, also dasselbe wie

i - 1

. Für

i

= 1 ist das 0.
Da kommt also erstmal raus:

int x = 1 + f1(0)

Du hast aber vorher schon herausbekommen, dass

f1(0)

0 zurückgibt.
Also steht da noch:

int x = 1 + 0

Nehmen wir einmal an, es würde

f1(3)

berechnet. Generell gibt die Funktion

f1(i)

ja entweder

i + f1(i - 1)

zurück, oder 0 für

i = 0

.

Daher ist

f1(3)

=

3 + f1(2)

=

3 + (2 + f1(1))

=

3 + (2 + (1 + f1(0)))

=

3 + (2 + (1 + 0))

=

6

 

[Biene88]

Achso, das heißt i ist immer mein festgesetzter Wert 1 und x ist die unbekannte Variable, dessen Ergebnis ich rausbekomme, wenn ich die Rekursion durchgegangen bin.

Wenn ich das jetzt richtig verstanden habe ist mit

int x = f1(10)

gemeint, das meine Rekursion bei 10 anfängt und sich durch

int x = i+f1(--i)

jeweils um 1 verringert, sodass ich letztendlich auf folgendes Ergebnis komme:

10 + (9 + (8 + (7 + (6 + (5 + (4 + (3 + (2 + (1 + 0))))))))) = 55

 

[CortPoker]

Auch noch nicht ganz. Das mit dem i hast du noch nicht ganz raus, wobei dein Ergebnis erstmal richtig ist Das i ist nicht der festgesetzte Wert 1, sondern der Parameter der Funktion f1(int i).
Du dekrementierst (d.h. verringerst um 1) mit jedem rekursiven Aufruf von f1 den Parameter i um 1. So wie du das geschrieben hast, hört sich das an, als würdest du den festen Wert i = 1 immer von der Funktion abziehen. Wäre aber nicht korrekt.
Das Ergebnis bleibt dasselbe, aber die Logik ist anders. Hoffe, das war einigermaßen nachvollziebar

 

[M_Schaffrath]

Du musst auch beachten, dass das

x

aus der

main()

-Methode nicht dasselbe

x

ist wie in der

f1()

-Methode.

Im Hauptprogramm steht nur: Weise der Variablen x den Rückgabewert der Funktion f1 mit dem Parameter 10 zu.

In f1 steht: Wenn der Parameter 0 ist, gib 0 zurück, ansonsten gibt die Summe des Parameters und des Rückgabewertes von f1 mit dem um eins verringerten Parameter zurück.

 

[Biene88]

Okay, das leuchtet ein.
Das heißt also durch den Datentyp int werden die beiden x seperat deklariert?
Würde also in der Zeile

int x = i+f1(--i)

nicht

int x

stehen, sondern nur x, dann wäre es dasselbe wie oben?

 

[M_Schaffrath]

Nein, eine Variable gilt nur für den Codeblock, in dem sie deklariert wurde. Nach der zugehörigen schließenden geschweiften Klammer hat Java sie vergessen. Ein Beispiel:

class Test{
	int klasse;
	
	public void eineMethode(){
		int methode;

		methode = klasse; // geht
		methode = schleife; // geht nicht
		
		for(int i = 0; i < 4; i++){
			int schleife = i;
		}
	}
}

Die Variable

klasse

ist in der Klasse deklariert. Damit ist sie dem ganzen Code, der in der Klasse steht bekannt und kann überall benutzt werden.
Die Variable

methode

ist innerhalb einer Methode deklariert worden. Damit kann sie innerhalb der Methode frei benutzt werden, aber außerhalb der Methode ist sie unbekannt.
Die Variable

schleife

wird im Codeblock der Schleife deklariert. Damit ist sie immer nur während eines Schleifendurchlaufs vorhanden, wird am Ende des Durchlaufs vergessen und beim nächsten Schleifendurchlauf wieder neu deklariert.

Darum funktioniert so etwas:

for(int i = 0; i < 10; i++){
		
}
	
for(int i = 0; i < 10; i++){
	for(int j = 0; j < i; j++){
		
	}
}

Die beiden for-Schleifen folgen hintereinander, daher kann die Zählvariable

i

zweimal deklariert werden: Sie ist außerhalb der Schleife unbekannt und jede der beiden Schleifen hat ihre eigenes

i

. Die for-Schleife innerhalb der zweiten for-schleife kann jedoch auf das

i

der zweiten Schleife zugreifen, da sie innerhalb des Schleifenblocks steht und daher das

i

kennt.

In deinem Fall gibt es ja zwei Methoden:

main()

und

f1()

. Jede von ihnen hat ihr eigenes

x

und kennt das der anderen nicht. Wenn du im Hauptprogramm ein x deklarierst, aber in der Funktionsmethode nicht, dann würde das einen Fehler geben, weil die Funktionsmethode noch nie von einem

x

gehört hat, aber damit arbeiten soll.

Wenn

x

in der Klasse deklariert wäre, könnten beide Methoden es benutzen. Allerdings macht das keinen Sinn, weil ja das x in jedem Anweisungsblock für etwas anderes steht. Um da die Übersicht zu behalten, macht es darum auch Sinn, seine Variablen nicht x, y, a, b, tmp, hilf, ding oder blubb zu nennen, sondern dann lieber "variableInDerDieZahlStehtDieNachherAusgegebenWerdenSoll" - dann kommt es nicht zu Verwechslungen.

 

[Biene88]

Das macht Sinn, wobei die Variablen trotzdem oft genutzt werden, aber dann hätte man hier ja schon statt zweimal x lieber ein x und noch eine andere Variable benutzt, dann wäre es nicht so verwirrend.

Aber ich habe immernoch nicht verstanden, ob ich mit meinem Ergebnis (55) jetzt am Ende bin? Die Rekursion habe ich jetzt bis zu 0 durchlaufen, muss ich jetzt nicht wieder ins Hauptprogramm zurück?

 

[M_Schaffrath]

Im Hauptprogramm wird ja nur gesagt:

Schreib das Ergebnis von f1(10) in die Variable x!

Das Programm ruft also sozusagen der Methode

f1()

rüber: "Hey, was kommt für 10 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 10 ist keine 0, das heißt, das Ergebnis ist 10 plus das, was für 9 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 9 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 9 ist keine 0, das heißt, das Ergebnis ist 9 plus das, was für 8 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 8 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 8 ist keine 0, das heißt, das Ergebnis ist 8 plus das, was für 7 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 7 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 7 ist keine 0, das heißt, das Ergebnis ist 7 plus das, was für 6 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 6 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 6 ist keine 0, das heißt, das Ergebnis ist 6 plus das, was für 5 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 5 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 5 ist keine 0, das heißt, das Ergebnis ist 5 plus das, was für 4 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 4 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 4 ist keine 0, das heißt, das Ergebnis ist 4 plus das, was für 3 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 3 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 3 ist keine 0, das heißt, das Ergebnis ist 3 plus das, was für 2 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 2 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 2 ist keine 0, das heißt, das Ergebnis ist 2 plus das, was für 1 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 1 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 1 ist keine 0, das heißt, das Ergebnis ist 1 plus das, was für 0 rauskommt. Die Methode ruft sich selbst zu: "Hey, was kommt für 0 raus?" und wartet auf eine Antwort.

Die Methode

f1()

überlegt: Hmm, 0 ist eine 0 und antwortet: "Kommt 0 raus!"

Die Methode

f1()

sagt sich: Cool, 1 + 0 ist 1 und antwortet: "Kommt 1 raus!"

Die Methode

f1()

sagt sich: Cool, 2 + 1 ist 3 und antwortet: "Kommt 3 raus!"

Die Methode

f1()

sagt sich: Cool, 3 + 3 ist 6 und antwortet: "Kommt 6 raus!"

Die Methode

f1()

sagt sich: Cool, 4 + 6 ist 10 und antwortet: "Kommt 10 raus!"

Die Methode

f1()

sagt sich: Cool, 5 + 10 ist 15 und antwortet: "Kommt 15 raus!"

Die Methode

f1()

sagt sich: Cool, 6 + 15 ist 21 und antwortet: "Kommt 21 raus!"


Und so weiter. Der Aufrufer wartet also immer auf sein Ergebnis und lässt die Methode in Ruhe rechnen. Bei Rekursion ist ja gerade die Idee, dass eine Methode sich immer und immer wieder aufruft, bis sie ein Ergebnis zurückbekommt und in dieser Zeit sozusagen zigmal auf sich selbst wartet. Wenn das Ergebnis da ist, bekommt jeder wartende Aufruf dann in umgekehrter Reihenfolge seine Antwort.

Wenn du meine "Geschichte" zu Ende schreibst, bekommt irgendwann das Hauptprogramm die Antwort von dem Aufruf, den es selbst gestartet hat und schreibt dann das Ergebnis in sein Variable x.

 

[hüteüberhüte]

Schreib doch einfach mal ein paar Ausgabeanweisungen rein:

    public static int f1(int i) {
        System.out.println(space(i) + "betrete f1, i=" + i);
        if (i == 0) {
            System.out.println(space(i) + "verlasse f1, i=" + i);
            return i;
        }
        int x = i + f1(--i);
        System.out.println(space(i + 1) + "verlasse f1, i=" + (i + 1) + ", x=" + x);
        return x;
    }

    public static String space(int i) {
        char[] c = new char[10 - i];
        Arrays.fill(c, ' ');
        return new String(c);
    }

...ergibt:

betrete f1, i=10
 betrete f1, i=9
  betrete f1, i=8
   betrete f1, i=7
    betrete f1, i=6
     betrete f1, i=5
      betrete f1, i=4
       betrete f1, i=3
        betrete f1, i=2
         betrete f1, i=1
          betrete f1, i=0
          verlasse f1, i=0
         verlasse f1, i=1, x=1
        verlasse f1, i=2, x=3
       verlasse f1, i=3, x=6
      verlasse f1, i=4, x=10
     verlasse f1, i=5, x=15
    verlasse f1, i=6, x=21
   verlasse f1, i=7, x=28
  verlasse f1, i=8, x=36
 verlasse f1, i=9, x=45
verlasse f1, i=10, x=55

...und dann sieht man schon, dass z.B. für f(10) 0+1+2+...+10 gerechnet wird...

(zu i habe ich 1 addiert, damit es nicht zu Verwechselungen kommt. i wird zwar vorher dekrementiert, das spielt aber beim verlassen der Methode keine Rolle mehr...)

 

[Biene88]

Oh man -.- Da muss man erstmal drauf kommen, aber so ist es mir bisher immer gegangen, ist die Aufgabe einmal fertig, hat man sie zwar verstanden, kann es beim nächsten mal aber wahrscheinlich nicht anwenden.

Mal sehen was in der Klausur kommt, aber vielen Dank für die Hilfe Euch allen