rekursiven Methode < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Tragen Sie die einzelnen Aufrufe der rekursiven Methode calc(…) der Reihe nach in die
ein (nur ein calc( … ) Aufruf pro Tabellenzeile) und geben Sie
die jeweiligen Rückgabewerte an. |
Guten Abend,
folgender Quelltext ist gegeben:
public class CalcSomething {
public static void main( String[] args ) {
System.out.println( calc(4, 2) );
}
public static int calc(int n, int k) {
if (k == 0 || n == k)
return 1;
else
return calc(n-1, k) + calc(n-1, k-1);
}
}
Ich hab den Quelltext mal bei Eclipse eingegeben und es kommt (beim Aufruf (4,2)) 6 raus. Ich versteh nicht ganz wieso? Es wird ja solange durchlaufen bis k==0 oder n==k ist oder?
Bitte helft mir auf die sprünge 
Viele Grüße
|
|
| |
|
Hallo!
Hast du dran gedacht, daß die Funktion sich wieder und wieder selbst aufruft, bis irgendwann die Abbruchbedingungen auftreten?
Du solltest sowas machen:
[mm] calc(4,2)=\underbrace{calc(3,2)}_{=\underbrace{calc(2,2)}_{=1}+\underbrace{calc(2,1)}_{=...}}+\underbrace{calc(4,1)}_{=\underbrace{calc(3,1)}_{=...}+\underbrace{calc(3,0)}_{=1}}
[/mm]
In der zweiten Zeile wird die Funktion vier mal aufgerufen, der erste und letzte Term führt dabei im nächsten Schritt zum Wert 1, die anderen beiden terme zweigen sich weiter auf...
|
|
|
| |
|
| Aufgabe | Tragen Sie die einzelnen Aufrufe der rekursiven Methode calc(…) der Reihe nach in die Tabelle
ein (nur ein calc( … ) Aufruf pro Tabellenzeile) und geben Sie
die jeweiligen Rückgabewerte an. |
Hallo,
Vielen Dank für deine Hilfestellung. Ich glaub ich habs nun
(3,2) + ( (3,1) )
( (2,2) + (2,1) ) + ( (2,1) + (2,0) )
( (1) + (1,1) + (1,0) ) + ( (1,1) + (1,0) + (1) )
( ( 1 + 1 +1 ) ) + ( (1 + 1 + 1) )
Was sind aber die einzelnen Aufrufe die ich dann in die Tabelle eintragen muss? Das hier?
4,2
3,2
3,1
2,2
2,1
2,0
1,1
1,0
|
|
|
| |
|
Hallo!
> (3,2) + ( (3,1) )
> ( (2,2) + (2,1) ) + ( (2,1) + (2,0) )
> ( (1) + (1,1) + (1,0) ) + ( (1,1) + (1,0) +
> (1) )
> ( ( 1 + 1 +1 ) ) + ( (1 + 1 + 1) )
Njaaaa, das ist etwas unübersichtlich, aber du meinst schon das richtige.
>
> Was sind aber die einzelnen Aufrufe die ich dann in die
> Tabelle eintragen muss? Das hier?
> 4,2
> 3,2
> 3,1
> 2,2
> 2,1
> 2,0
> 1,1
> 1,0
Nein, ich denke, das stimmt nicht ganz.
Der erste Aufruf ist calc(4,2). Dieses ruft zunächst calc(3,2) auf, dieses ruft calc(2,2) auf. Das calc(2,2) gibt 1 zurück an calc(3,2). calc(3,2) ruft dann erst calc(3,1) auf, welches...
Die ganze Zeit über wartet calc(4,2) immernoch darauf, endlich einen Rückgabewert von calc(3,2) zubekommen, um anschließend calc(3,1) aufzurufen, zu warten bis da was zurück kommt, und anschließend die Summe zurückzugeben.
Klar? es wird immer erst der linke Summand berechnet, dann der rechte, und die Summe zurückgegeben. Und ich vermute, deine Tabelle soll die Aufrufe in chronologischer Reihenfolge enthalten.
Nebenbei: Warum trägst du in dein Programm nicht mal die Ausgabe von n und k in die Funktion ein? Dann bekommst du genau das.
|
|
|
|
