Rekursion in Java < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich lerne im Moment Java. In meinem Buch taucht nun unter dem Thema rekursion folgender code auf:
static long cn ( long n ) {
return n == 0 ? 1 : ( 4 ( n−1) + 2) cn ( n−1) / ( n + 1 ) ;
}
Kann mir jemand erklären was in dem Codestück genau gemacht wird?
es handelt sich ja um eine rekursive Funktion.
ich verstehe es so: wenn n 0 ist, dann soll 1 : ( 4*( n−1) + 2)*cn ( n−1) / ( n + 1 ) berechnet werden und an die Funktion zurückgegeben werden. Stimmt das so?
Welcher rekursionsart kann ich das denn dann zuordnen?
Es gibt ja nur einen funktionsaufruf und es hat eine eindeutige Struktur die ich für geradlinig halte. Müsste es dann nicht eigentlich eine lineare rekursion sein?
Danke schonmal :)
|
|
| |
|
Hallo!
Zunächst hast du hier den Fragezeichenoperator vor dir.
Die Anweisung
<Resultat>=<Bedingung>?<Ausdruck1>:<Ausdruck2>
ist gleichbedeutend mit
if(<Bedingung> == True){
<Resultat>=<Ausdruck1>
}
else{
<Resultat>=<Ausdruck2>
}
Das heißt in deinem konkreten Fall:
Wenn n=0 ist, gib sofort den Wert 1 zurück, ansonsten das Ergebnis dieses Rechenausdrucks, innerhalb dessen die Funktion selbst aufgerufen wird.
Da es nur einen rekursiven Aufruf der Funktion gibt, ist die Rekursion linear, und da der Parameter in Einerschritten verkleinert wird, ist das eine primitiv-lineare Rekursion.
|
|
|
| |
|
Vielen Dank!
Das habe ich nun soweit kapiert.
Wie könnte ich denn jetzt zeigen, dass diese Funktion terminiert.
Normalerweise ja mit einer Terminierungsfunktion und dann erklären wieso die Terminierungsfunktion irgendwann eine untere Schranke hat, weil zb n >0 vorgegeben ist oder so.
Aber was ich nicht ganz verstehe ist wie ich jetzt bei dieser Funktion eine Terminierungsfunktion finde.
Wäre nettm wenn mir das mal jm an nem Beispiel zeigen könnte, damit ich das endlich verstehe.
Liebe Grüße und Danke!
|
|
|
| |
|
Hallo!
Die terminierung findet doch dadurch statt, daß das Argument der Funktion bei jedem Aufruf um 1 vermindert wird. Sobald es =0 ist, erfolgt kein weiterer rekursiver Aufruf, und damit hast du die Terminierung erreicht.
Zur Not berechne doch mal per hand den Wert von cn(4).
|
|
|
| |
|
Danke!
Okay soweit ist es mir jetzt klar.
könnte ich dann einfach cn (4) = 42 als Terminierungsfunktion nehmen oder wie macht man eine Terminierungsfunktion?
|
|
|
| |
|
Hallo BlackSalad,
> Danke!
>
> Okay soweit ist es mir jetzt klar.
>
> könnte ich dann einfach cn (4) = 42 als
> Terminierungsfunktion nehmen oder wie macht man eine
> Terminierungsfunktion?
>
Siehe hier:![[]](/images/popup.gif) wp-Kalkül
Gruss
MathePower
|
|
|
|
