Rekursionsaufrufe in Java

Computer: Software & Programmierung Java
#1

Hallo,

ich habe eine Frage zu einer übungsaufgabe in Java. Es geht dabei um Rekursionsaufrufe (Lösung liegt bei). Ich habe euch hier mal eine Foto hochgeladen:

http://img89.imageshack.us/img89/2069/rekursion.jpg

Nun kann ich mir leider nicht zusammenreimen, wie die einzelnen Aufrufe entstehen. Außerdem wäre es toll, wenn mir jemand sagen könnte, woran ich die maximale Rekursionstiefe erkenne (also die anzahl der maximal aktiven Aufrufe). Und woher weiß ich, wann der Rekursive Aufruf stoppt? Für eine Antwort wäre ich euch echt dankbar :wink:

Viele Grüße
NikeAir22

#2

Ausgehend von dem Code erfolgt ein rekursiver Aufruf nur wenn gilt:

  1. x >= 2
  2. y > 2
    Ist das erfüllt werden für den nächsten Aufruf x und y neu ermittelt:
  3. x := x-2, y := y/3
  4. x := x-1, y := y+1
#3

Hallo zurück.

Leider ist der Chef gerade wegen eines Projekts in England unterwegs, so dass ich Ihre Anfrage zunächst beantworten muss. Ich muss Sie leider bitten, Ihre Anfrage ggf. noch einmal Ende April zu übersenden; dann ist Herr Meyer wieder zurück.

Mit freundlichen Grüßen
i.A.
Anja Brämer-Wiehe
Assistenz der Geschäftsführung

#4

Schau Dir halt den Code genau an:
Rekursion heisst, dass sich eine Funktion selbst aufruft.
Das ist in genau einer Zeile des Beispiels der Fall.
Sonst gibt die Funktion sofort einen Wert zurück, der kein Ergebnis eines Aufrufs von f ist.
Gesteuert wird dieses Verhalten über die Bedingungen der ifs.
Die maximale Rekursionstiefe ist von den übergebenen Parametern abhängig. Du untersuchst ganz einfach, ob mit dem Wertepaar (5, 4) und den daraus entstehenden neuen Parametern für die eventuellen weiteren Aufrufe die Funktion nochmal aus sich heraus aufgerufen wird.

#5

Hallo,

erfordert bischen Nachdenken.
Und Probieren.
Weil es relativ einfach nachzuvollziehen ist.

Funktion:

static int f(int x, int y) {
 if (x

Die Funktion wird mit f(5,4) aufgerufen.
Eine Rekursion (also erneutes Aufrufen der Funktion) geschieht nur unter else (bei if und else if wird blos ein Wert zurückgegeben, die Funktion aber nicht noch mal aufgerufen).

============================================================
1.Aufruf Iteration 1
If und else if bedingung nicht erfüllt, also else
das wäre dann, wenn man die vorgegebenen Werte benutzt, Folgendes:
return 2\*f(5-2,4/3) + f(5-1,4+1); oder
return 2\*f(3,1) + f(4,5);
============================================================
Und da hast du Aufruf 2 f(3,1)
und Aufruf 3 f(4,5)
In dieser Zeile wird die Funktion gleich 2 Mal!! aufgerufen.
Du hast jetzt den Ausgangsaufruf der Funktion und 2 Aufrufe gleichzeitig dazu.
Also Iteration 3

So nun machst du das Selbe, wie bei Aufruf 1 mit Aufruf 2 und 3. Und du wirst sehen bei Aufruf 3 bekommst du erneute Funktionsaufrufe

Prinzip begriffen? Probier einfach weiter...

Torsten
#6

Hallo,

Du musst „nur“ die Definition
f(x,y) = \left{\begin{array}{ll}
1 & \mbox{f"ur} x
einsetzen, die besagt, dass die Rekursion stoppt, wenn x

#7

Hallo

Also als Tipp. Mache mal die klammern um die If und else Anweisungen.

Das Problem ist nicht das man nicht sieht wie die tiefe ist sondern das die Zusammensetzung nicht klar sichtbar ist.

#8

Moin,
die einzelnen Aufrufe entstehen, wenn die Funktion sich selbst aufruft. Die unterste return-Zeile enthält zweimal die Funktion selbst. Bei den Werten musst du beachten, dass die Funktion ein int entgegen nimmt, und int kann nur ganze Zahlen speichern:
f(5,4) würde eig einmal f(5-2, 4/3) = f(3, (1,3) ) aufrufen,aber die „,3“ werden abgeschnitten, wenn der Wert in einer int-Variable gespeichert wird. Also bleibt nur die 1 über: f(3,1). Der nächste Aufruf ist in der rechten Seite der Zeile, das F(x-1,y+1), was zu F(4,5) wird. F(3,1) gibt dann 2 zurück, weil y

#9

Hallo,

woher weiß ich, wann der Rekursive Aufruf stoppt?

die leichteste Frage zuerst: Du merkst, dass die Rekursion beendet ist, wenn du eine Konstante zurückgibst, hier also „return 1“ bzw. „return 2“, d.h., wenn x

#10

Hi,

Vielen Dank für deine Antwort. Es wäre echt toll von dir, wenn du mir diesen Gefallen tun könntest und das ganze noch mal verständlich aufzeichnen würdest :wink:

Viele Grüße
NikeAir22

#11

Hallo,

ich habe eine Frage zu einer übungsaufgabe in Java. Es geht
dabei um Rekursionsaufrufe (Lösung liegt bei). Ich habe euch
hier mal eine Foto hochgeladen:

http://img89.imageshack.us/img89/2069/rekursion.jpg

Nun kann ich mir leider nicht zusammenreimen, wie die
einzelnen Aufrufe entstehen.
Viele Grüße
NikeAir22

Hallo,
ich habe das Ganze mal zu einer Java-Klasse zusammengeschrieben und mit 2 diagnostischen Variablen versehen. Das Programm sieht dann wie folgt aus:

/**
* Test für eine Rekursion
*
* @author Volkert Anton
*
*/
public class Rekursion {
static int rek = 1;
static int aufrufe = 0;
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(f(5,4)+ " Rekursionstiefe= "+rek+ " Aufrufe= "+aufrufe);
}
/**
* rekursive Methode
*/
static int f(int x,int y) {
aufrufe++;
if (x

#12

Hallo NikeAir,

Ich habe den Lösungsweg eben kurz auf Papier aufgemalt und abfotografiert. Ich hoffe du kannst was erkennen:

http://img593.imageshack.us/img593/7024/201302271618…

Anmerkungen:

  • Bei dem else-Fall wird immer zuerst der erste Funktionsaufruf verarbeitet und danach der 2.
    -> erst orange, dann blau.
  • Sobald beide Werte ermittelt wurden, wird das Ergebnis berechnet und zurückgegeben
  • Es handelt sich um Integer Divisionen, deshalb ergibt z.b. im ersten Aufruf 4/3 = 1

Zu deinen Fragen:
Sobald die Abbruchbedingung(en) (hier: die if und if-else Bedingungen) erfüllt werden, geht der jeweilige Zweig „rückwärts“.
Die maximale Rekursionstiefe erkennt man erst, wenn man die Rekursion durchgeht.

Hoffe du verstehst das Bild :smile:

Grüße

#13

Hi,

ich glaube ich habe dir schon geantwortet, aber in meinem Profil steht es noch als offene Frage …

Mein Tipp zum Verständnis von Rekursion: versuche wie ein Computer Schritt für Schritt vorzugehen. Schreib dir vielleicht auf einem Zettel jeden Schritt mit. Also jedes Mal, wenn ein neuer Schleifendurchlauf beginn schreibst du dir die Schleife wieder auf deinen Zettel, usw. Dann verstehst du, was der Computer macht.

Liebe Grüße,
Philipp