Java Erklärung Beispiel Rekursion

Rekursion in Java-Erklärung anhand eines Beispiels

Von: , 03.01.2010 19:38 Uhr

Hallo zusammen,
ich sitze seit Minuten über 2 Aufgaben, die ich zur Übung lösen soll.
Die Aufgabenstellung lautet: Betrachten Sie das folgende Java-Programm und geben Sie an, was das Programm ausdruckt.

public class Aufgabe1
{
public static void main(String[] args)
{
System.out.println("f = "+f(2345,1234));
}
public static int f(int n, int m)
{
if (n%m == 0) return 0;
return 2*f(n-1, m-1);
}
}

public class Aufgabe2
{
public static int f(int n)
{
if (n<2) return 1;
return 1+f(n/2);
}
public static void main(String[] args)
{
System.out.println("f(1000) = "+ f(1000));
}

}


Ich besitze zwar die Lösungen zu den Aufgaben - verstehe aber aufgrund der Rekursion nicht, wie ich auf die Ausgabe kommen soll!
Aufgabe 1: f(1000)=10
Aufgabe 2:f = 0

Kann mir jemand bitte erklären, wie ich die einzelnen Rekursionsschritte (rekursiver Abstieg und rekursiver Aufstieg) im Kopf nachvollziehen kann?
Vielen Dank im vorraus!

2 Antworten zu dieser Frage

1. Antwort von nach 2 Tagen 0 hilfreich

   Re: Rekursion in Java-Erklärung anhand eines Beispiels

   Hallo,
   
   ich hoffe meine Antwort kommt noch rechtzeitig.
   
   Aufgabe 1 ist simpel. Die statische Funktion f liefert bei der Abbruchbedingung den Wert 0. Entweder ist diese Abbruchbedingung gleich beim ersten Aufruf erfüllt, dann ist das Ergebnis 0. Andernfalls wird der erste Rekursionsschritt ausgeführt, eine Multiplikation:
   2*f(n-1, m-1)
   
   Für den Fall dass die Abbruchbedingung irgendwann erfüllt ist ergibt dies 0! Grund: irgendwann liefert die Funktion f ja den Wert 0, und 0 mal irgendwas (sprich das Ergbnis der davor ausgeführten Rekursionsschritte) ergibt 0.
   
   
   
   Aufgabe 2:
   Hier sieht die Aufrufreihenfolge wie folgt aus, wobei r nur die Funktionsaufrufe durchnummeriert:
   
   r | Berechnung
   ---------------------
   1 | f(1000)
   2 | 1 + f(500)
   3 | 1 + 1 + f(250)
   4 | 2 + 1 + f(125)
   5 | 3 + 1 + f(62) [125 /2 = 62.5 ergibt als int 62]
   6 | 4 + 1 + f(31)
   7 | 5 + 1 + f(15)
   8 | 6 + 1 + f(7)
   9 | 7 + 1 + f(3)
   10 | 8 + 1 + f(1) --> Abbruchbedingung, da 1<2 wird 1 zurückgegeben
   11 | 9 + 1 = 10
   
   
   
   Falls du es nochmal mit PC überprüfen willst, kannst du ja in den Funktionen f eine Ausgabe einbauen, damit du siehst wie der nächste Rekursionsschritt lautet.
   
   Gruß,
   Tom
   

   • Antwort von nach 6 Tagen 0 hilfreich

     Re^2: Rekursion in Java-Erklärung anhand eines Beispiels

     Hey Tom,
     vielen Dank für deine sehr hilfreiche Erklärung, wenn du mir jetzt noch zeigen könntest, wo ich die Ausgabe (und wie) einfügen muss - wär´s perfekt.
     
     MfG
     Dan
     

Jetzt auf diese Frage antworten.