Rekursive Methode

Status
Nicht offen für weitere Antworten.
J

jhonnyb

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

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

SlaterB

Gast
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?
 
J

jhonnyb

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

SlaterB

Gast
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
 
J

jhonnyb

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

SlaterB

Gast
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..
 
J

jhonnyb

Mitglied
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
Code:
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
 
S

SlaterB

Gast
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
 
J

jhonnyb

Mitglied
Hallo,

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

Geeeee

Bekanntes Mitglied
so, oder?
Code:
                                        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 :D
 
Zuletzt bearbeitet:
E

ElfenTraene

Gast
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
Code:
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??
 
E

ElfenTraene

Mitglied
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?
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
G Rekursive Methode Java Basics - Anfänger-Themen 3
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
G Rekursive Methode Java Basics - Anfänger-Themen 5
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
G Rekursive Methode Java Basics - Anfänger-Themen 7
veryck Methoden Rekursive Methoden mit Rückgabeparameter Java Basics - Anfänger-Themen 9
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
M Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
R Rekursive Ausgabe eines Binärbaums Java Basics - Anfänger-Themen 4
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
K Rekursive Methoden Java Basics - Anfänger-Themen 15
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
N rekursive Beispiele Java Basics - Anfänger-Themen 3
ven000m Rekursive Funktionen - Frage Java Basics - Anfänger-Themen 16
D rekursive ausgabe einer zahl Java Basics - Anfänger-Themen 14
S Rekursive Funktionen in imperative Funktionen umwandeln Java Basics - Anfänger-Themen 2
M Rekursive Binärsuche Java Basics - Anfänger-Themen 6
S rekursive methoden Java Basics - Anfänger-Themen 5
J Methoden Frage: Array-Werte in anderer Methode ändern Java Basics - Anfänger-Themen 4
S HashMap contains() Methode Java Basics - Anfänger-Themen 1
F Methoden Methode richtig aufrufen Java Basics - Anfänger-Themen 3
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
JD_1998 Random Array sortieren mit Hilfe einer Methode Java Basics - Anfänger-Themen 4
T Methode implementieren Java Basics - Anfänger-Themen 21
JD_1998 Vorgegebene Methode erweitern um Hex -> Dezimal umzuwandeln Java Basics - Anfänger-Themen 1
A While Schleife - buubelsort methode Java Basics - Anfänger-Themen 2
NeoLexx equals()-Methode Verständnis Frage anhand Code Beispiel Java Basics - Anfänger-Themen 22
X compareTo Methode wird ignoriert Java Basics - Anfänger-Themen 7
B Wie kann ich etwas vor der Main-Methode ausführen? Java Basics - Anfänger-Themen 21
J Methode als Class anlegen Java Basics - Anfänger-Themen 7
K Übergabe von Werten (zweidimensionales Array) aus einer Methode an zweidimensionales Array in main() Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Anzeige


Oben