Rekursionsaufgabe

Biene88

Mitglied
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
Code:
int A(int n)einfügen
n=0. Dann steht in der nächsten Zeile
Code:
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
Code:
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
Code:
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
Code:
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
 
Zuletzt bearbeitet von einem Moderator:
S

SlaterB

Gast
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

Aktives Mitglied
Nun setze ich i=1.
Damit rutsche ich in die nächste Zeile
Code:
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.
Code:
i
hat den Wert 1.
Code:
--i
ist der um 1 verringerte Wert von
Code:
i
, also dasselbe wie
Code:
i - 1
. Für
Code:
i
= 1 ist das 0.
Da kommt also erstmal raus:
Code:
int x = 1 + f1(0)
Du hast aber vorher schon herausbekommen, dass
Code:
f1(0)
0 zurückgibt.
Also steht da noch:
Code:
int x = 1 + 0


Nehmen wir einmal an, es würde
Code:
f1(3)
berechnet. Generell gibt die Funktion
Code:
f1(i)
ja entweder
Code:
i + f1(i - 1)
zurück, oder 0 für
Code:
i = 0
.

Daher ist
Code:
f1(3)
=
Code:
3 + f1(2)
=
Code:
3 + (2 + f1(1))
=
Code:
3 + (2 + (1 + f1(0)))
=
Code:
3 + (2 + (1 + 0))
=
Code:
6
 

Biene88

Mitglied
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
Code:
int x = f1(10)
gemeint, das meine Rekursion bei 10 anfängt und sich durch
Code:
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

Aktives Mitglied
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

Aktives Mitglied
Du musst auch beachten, dass das
Code:
x
aus der
Code:
main()
-Methode nicht dasselbe
Code:
x
ist wie in der
Code:
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

Mitglied
Okay, das leuchtet ein.
Das heißt also durch den Datentyp int werden die beiden x seperat deklariert?
Würde also in der Zeile
Code:
int x = i+f1(--i)
nicht
Code:
int x
stehen, sondern nur x, dann wäre es dasselbe wie oben?
 

M_Schaffrath

Aktives Mitglied
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:

Java:
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
Code:
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
Code:
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
Code:
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:
Java:
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
Code:
i
zweimal deklariert werden: Sie ist außerhalb der Schleife unbekannt und jede der beiden Schleifen hat ihre eigenes
Code:
i
. Die for-Schleife innerhalb der zweiten for-schleife kann jedoch auf das
Code:
i
der zweiten Schleife zugreifen, da sie innerhalb des Schleifenblocks steht und daher das
Code:
i
kennt.

In deinem Fall gibt es ja zwei Methoden:
Code:
main()
und
Code:
f1()
. Jede von ihnen hat ihr eigenes
Code:
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
Code:
x
gehört hat, aber damit arbeiten soll.

Wenn
Code:
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

Mitglied
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

Aktives Mitglied
Im Hauptprogramm wird ja nur gesagt:
Code:
Schreib das Ergebnis von f1(10) in die Variable x!
Das Programm ruft also sozusagen der Methode
Code:
f1()
rüber: "Hey, was kommt für 10 raus?" und wartet auf eine Antwort.

Die Methode
Code:
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
Code:
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
Code:
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
Code:
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
Code:
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
Code:
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
Code:
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
Code:
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
Code:
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
Code:
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
Code:
f1()
überlegt: Hmm, 0 ist eine 0 und antwortet: "Kommt 0 raus!"

Die Methode
Code:
f1()
sagt sich: Cool, 1 + 0 ist 1 und antwortet: "Kommt 1 raus!"

Die Methode
Code:
f1()
sagt sich: Cool, 2 + 1 ist 3 und antwortet: "Kommt 3 raus!"

Die Methode
Code:
f1()
sagt sich: Cool, 3 + 3 ist 6 und antwortet: "Kommt 6 raus!"

Die Methode
Code:
f1()
sagt sich: Cool, 4 + 6 ist 10 und antwortet: "Kommt 10 raus!"

Die Methode
Code:
f1()
sagt sich: Cool, 5 + 10 ist 15 und antwortet: "Kommt 15 raus!"

Die Methode
Code:
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

hüteüberhüte

Gast
Schreib doch einfach mal ein paar Ausgabeanweisungen rein:

Java:
    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:

Code:
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...)
 
Zuletzt bearbeitet von einem Moderator:

Biene88

Mitglied
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 :) :) :)
 

Neue Themen


Oben