Rekursive Methode

[jhonnyb]

Hallo,
ich bin neu hier wie ihr sicherlich sehen könnt. ;-)
Ich habe bei folgendem Code ein Verständnissproblem.

public class CalcSomething {
public static void main( String[] args ) {
System.out.println( calc(4, 3) );
}
public static int calc(int n, int k) {
if (k == 0 || n == k)
return 1;
else
return calc(n-1, k-1) + calc(n-2, k-1) + calc(n-1, k);
}
}

und zwar int n=4 und k=3 das ist doch richtig oder?
Wenn ich den Code ausführe kommt 7 raus.
kann mir jemand erklären warum?

Viele Grüße

 

[SlaterB]

calc(4, 3) = in erster Rekursion calc(3, 2) + calc(2, 2) + calc(3, 3)

davon sind die letzten beiden glücklicherweise jeweils 1, also gehts recht schnell:

calc(4, 3)
= calc(3, 2) + calc(2, 2) + calc(3, 3)
= calc(3, 2) + 2
= calc(2, 1) + calc(1, 1) + calc(2, 2) +2
= calc(2, 1) + 4
= calc(1, 0) + calc(0, 0) + calc(1, 1) +4
= 1 + 2 +4
= 7

das kannst du doch auch selber Stück für Stück ausrechnen?

 

[jhonnyb]

Hallo,
Vielen Dank für deine schnelle Antwort.
Wie schon gesagt, habe da ein kleines Verständniss Problem..
Wusste nicht wie ich das ausrechnen sollte. Aber danke das du mir es erklärt hast

calc(4, 3)
= calc(3, 2) + calc(2, 2) + calc(3, 3)
= calc(3, 2) + 2
= calc(2, 1) + calc(1, 1) + calc(2, 2) +2
= calc(2, 1) + 4
= calc(1, 0) + calc(0, 0) + calc(1, 1) +4
= 1 + 2 +4
= 7

habe noch ein paar Fragen...und zwar warum wird das immer um 1,1 verringert? also calc(2,2) zu calc(1,1) zu calc(0,0)

Tragen Sie die einzelnen Aufrufe der rekursiven Methode calc(…) in der Reihenfolge ihres
Aufrufs ein.

Was für welche Ausrufe sind da gemeint?
calc(3,2),calc(2,1) und calc (1,0)?

Viele Grüße

 

[SlaterB]

um 1,1 wird es verringert, weil im Quellcode vorgegeben:
> return calc(n-1, k-1) + ..

warum das dort so steht, kann ich nicht sagen

jedenfalls wird deswegen aus calc(4, 3)
= calc(3, 2) + weitere Summanden, siehe Quellcode

-------

> calc(3,2),calc(2,1) und calc (1,0)?

calc(2, 2) auch usw, alle

 

[jhonnyb]

Hallo nochmals..
Ah ja stimmt. Ok das ist jetzt klar warum es sich um 1,1 verringert..

Ich habe wohl irgendwie Probleme damit die rekursive Methode im Kopf durchzudenken

Ich habe noch einen ähnlichen Code da ist mir auch nicht klar wie es zu dem Ergebniss(32) kommt, kann es mir da eventuell nochmals vorrechnen.
Vielleicht geht mir dann hoffentlich ein Licht auf

public class CalcSomething {
public static void main( String[] args ) {
System.out.println( c( 2, 5 ) );
}
public static int c( int a, int b ) {
return ( b == 0 ) ? 1 : a * c( a, b-1 );
}
}

Das Programm läuft solange durch bis c(2,0) ist oder?

Viele Größe

 

[SlaterB]

genau, dann kommt die 1 und durch die vorherigen Rekursionsschritte 5x *2,
also 2^5 = 32,

wenn dir das so wirklich leichter ist als selber auszuprobieren..

 

[jhonnyb]

Hallo,
ich probier es natürlich auch aus und lass es mir durch den Kopf gehen.
Nur der Ansatz hat mir gefehlt...
a=2, b=5

return ( b == 0 ) ? 1 : a * c( a, b-1 );

--> return(b==0)? 1: 2*(2,5-1) versteh ich das so richtig?<--



Nochmal zu dem ersten Programm

Tragen Sie die einzelnen Aufrufe der rekursiven Methode calc(…) in der Reihenfolge ihres
Aufrufs ein.

Das sind die Folgene oder?
4,3
3,3
3,2
2,2
2,1
1,1
1,0
0,0

 

[SlaterB]

als erstes kommt immer die doppelte -1-Verkleinerung,
also erstmal
4,3
3,2
2,1
1,0

kannst auch ein System.out.println zu Beginn der Methode setzen

> return(b==0)? 1: 2*(2,5-1) versteh ich das so richtig?

so geht das ab, ja

 

[jhonnyb]

Hallo,

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 habe wieder mal einen Code
calc (4,2) in erster Rekursion =
calc(3,2) + calc(3,1)
calc (2,2)+calc(2,0)
1 + 1
calc(1,2) + calc(1,-1) + 2
ist der Ansatz so richtig?

 

[Geeeee]

so, oder?

                                        calc(4,2)
                               calc(3,2)   +    calc(3,1)
              (calc(2,2) + calc(2,1))      + (calc(2,1) + calc(2,0))
(( 1 ) +  (calc(1,1) + calc(1,0)))         + (((calc(1,1)+ calc(1,0)) + (1))
(( 1 ) + (1) + (1) )                       +  ((1) + (1) +(1) )

Ich hoffe der "Baumeffekt" spricht für sich

 

[ElfenTraene]

Hallo,
ich probier es natürlich auch aus und lass es mir durch den Kopf gehen.
Nur der Ansatz hat mir gefehlt...
a=2, b=5

return ( b == 0 ) ? 1 : a * c( a, b-1 );

--> return(b==0)? 1: 2*(2,5-1) versteh ich das so richtig?<--



Nochmal zu dem ersten Programm

Das sind die Folgene oder?
4,3
3,3
3,2
2,2
2,1
1,1
1,0
0,0

Ich hab noch eine Frage und wie lauten dann die Rekursive Aufrufe von c(..) bei der Aufgabe CalcSomething von oben??

 

[ElfenTraene]

Bräuchte nochmal Hilfe mit dieser Aufgabe:

public class CalcSomething {
public static void main( String[] args ) {
System.out.println( c( 2, 5 ) );
}

public static int c( int a, int b) {
return ( b == 0 ) ? 1 : a * c( a, b-1);
}
}


Wir sollen die Aufrufe der rekursiven Methode c() in eine Tabelle eintragen und die jeweiligen Rückgabewerte.

Das Ergebnis ist ja 32 sprich 2^5. Mein a ist 2 und mein b 5 oder? Jetzt ist mir aber nicht klar wie man das aufschreiben soll. Es müssen insgesamt 6 rekursive Aufrufe sein.
Habe bisher nur das: (b == 0) ? 1 : 2 * c( 2, 5-1).

Bitte wer kann mir helfen und das erklären?