[Java] Endrekursive Funktion

xlemmingx · 31. Mai 2011

Endrekursive Funktion

Hi,

ich hab ein kleines Problem damit, eine rekursive Funktion in eine endrekursive umzuschreiben, damit man sie dann automatisch iterativ formulieren kann.

lineare rekursive Funktion zur Berechnung der Catalan-Zahlen:

Code:

static long cn(long n)
{
 if(n == 0)
 return 1;
 else
 return (4*(n-1)+2)*cn(n-1) / (n+1);
}

Mein Ansatz für die endrekursive Fassung:

Code:

static long cnend(long n)
{
 return cn2(1,n);
}

static long cn2(long m,long n)
{
 if(n==0)
 return m;
 else
 {
 m = (4*(n-1)+2)*m/(n+1);
 return cn2(m, n-1);
 }
}

Aber die Ergebnisse stimmen ab n=3 nicht mehr überein und ich finde partout den Fehler nicht. Wäre super wenn mir da jemand auf die Sprünge helfen könnte

Noch die komplette Datei zum testen:

Code:

public class rekursiv
{
static long cn(long n)
{
 if(n == 0)
 return 1;
 else
 return (4*(n-1)+2)*cn(n-1) / (n+1);
}

static long cnend(long n)
{
 return cn2(1,n);
}

static long cn2(long m,long n)
{
 if(n==0)
 return m;
 else
 {
 m = (4*(n-1)+2)*m/(n+1);
 return cn2(m, n-1);
 }
}

public static void main(String[] args)
{
 int cat = Integer.parseInt(args[0]);
 System.out.println(cn(cat));
 System.out.println(cnend(cat));
}
}

Das am war natürlich ein Tippfehler.

MfG xlemmingx

Anzeige

SchOudeBläS · 31. Mai 2011

AW: Endrekursive Funktion

Weiß jetzt nicht ob das schon dein Fehler ist, aber unten in der Datei hast du in der Zeile m = (4*(n-1)+2)*am/(n+1); wohl anstatt m am geschrieben...

Müsste ja aber auch beim Compilieren nen Fehler geben

JSee · 31. Mai 2011

AW: Endrekursive Funktion

Der Fehler kommt daher, dass du n in jedem Schritt verringerst. Mal ein Beispiel für n = 3:

Du übergibst m = 1 und n = 3 an cn2. Es müsste aber m = 2 sein, da cn(2) = 2 ist bzw. m halt immer das Ergebnis der vorherigen Berechnung sein muss. Das neue m berechnet sich momentan bei dir für n = 3 so: m = (4*(3-1)+2)*1/(3+1) = 10/5 = 2. Es müsste aber m = (4*(3-1)+2)*2/(3+1) = 10*2/4 = 5 sein.
Hoffe du siehst den Fehler.

xlemmingx · 1. Juni 2011

AW: Endrekursive Funktion

Danke, jetzt seh ich das Problem. Hab versucht das zu lösen indem ich einen zusätzlichen Parameter übergebe mit dem ich dann hochzählen kann, also praktisch von unten nach oben, nicht von oben nach unten wie vorher.
Jetzt stimmt die Berechnung bis n=4 aber nicht weiter oO

Code:

static long cnend(long n)
{
 return cn2(1,n,1);
}

static long cn2(long m,long n, int a)
{
 if(a==n)
 return m;
 else
 {
 m = (4*(n-1)+2)*m/(n+1);
 return cn2(m, n, a+1);
 }
}

failsafe · 1. Juni 2011

AW: Endrekursive Funktion

Nur mal nebenbei: Das ganz iterativ zu formulieren ist doch trivial:

Code:

long cn_iter(long N) {
 long cn = 1;
 for(long n=1; n<=N; ++n) {
 cn = (4*(n-1)+2)*cn / (n+1);
 }
 return cn;
}

Hab alles Ergebnisse für N = 0 bis 65535 mit Deinen Ergebnissen geprüft. Passt und ist etwa...1000mal schneller
Vielleicht hilft es Dir ja.

EDIT:
Ich hab gelogen. Es ist nur etwas schneller Aber immerhin schneller!

xlemmingx · 1. Juni 2011

AW: Endrekursive Funktion

Hilft mir nicht wirklich weiter, weil ich wie gesagt erstmal eine endrekursive Funktion brauche..

Mit iterativen Funktionen hab ich auch kein Problem, nur die Rekursion schafft mich.

failsafe · 1. Juni 2011

AW: Endrekursive Funktion

Ich kanns jetzt auf die Schnelle nur "Vorwärts". Folgende Endrekursion funktioniert auf jeden Fall für die ersten 65535 Fälle:

Code:

long cn_x(long current, long n, long N) {
 if(n == N+1) {
 return current;
 }
 long c = (4*(n-1)+2) * current / (n+1);
 return cn_x(c, n+1, N);
}

long cn_end(long N) {
 if(N==0) return 1;
 return cn_x(1, 1, N);
}

Edit: Heh, ist ja fast, was Du auch hattest. Aber N+1

xlemmingx · 6. Juni 2011

AW: Endrekursive Funktion

Also wirklich nur die Abbruchbedingung falsch oO

Besten Dank!

MfG xlemmingx

Nützliche Suchen

[Java] Endrekursive Funktion

Videos zum Themenbereich