Terminierungsfunktion

[BlackSalad]

Hallo,

leider weiß ich nicht so wirklich wo ich infos darüber finden soll. Vielleicht könnt ihr mir das erklären.

Wie stellt man denn eine Terminierungsfunktion auf?

also wenn ich jetzt ne Funktion habe:

static long fakultaet2(int n) { 
        return (n == 1) ? 1 : (n * fakultaet2(n – 1)); }

und wie komme ich dann auf die Terminierungsfunktion t(x)=x ?


Wie stelle ich so eine Terminierungsfunktion auf und was bedeutet das überhaupt genau?

Ich weiß nur, dass die Terminierungsfunktion zeigt, dass die Funktion terminiert, also endet.

 

[SlaterB]

Rekursion – Terminierungsfunktionen

Terminierung kann folgendermaßen gewährleistet werden:
man gibt eine Maßfunktion f auf den Parameterwerten an, so
dass

die Werte von f natürliche Zahlen in N sind und
der f-Wert des Parameters jedes rekursiven Aufrufs echt kleiner ist
als der f-Wert des Parameters des ursprünglichen Aufrufs.
Da N nach unten durch 0 beschränkt ist, muss ein Aufruf mit
Parameter p spätestens nach f(p) rekursiven Aufrufen
enden.
Eine solche Funktion heißt Terminierungsfunktion für den
Algorithmus.

http://www.google.de/url?sa=t&sourc...sg=AFQjCNHD1cWC9rQP1s6KegMOasz-EAlCtQ&cad=rja

das gilt hier offensichtlich

der Java-Code selber ist ja quasi schon eine mathematische Funktion,
t(x) ist = 1 wenn x == 1 sonst ..

 

[BlackSalad]

okay. Danke.


und wie kommt man auf die Argumente?


x, x−1, x−2, x-3, …


wie kann ich die denn berechnen?

 

[SlaterB]

du musst nix zu x, x-1 usw. berechnen, was läßt dich dies vermuten?
"t(x) ist = 1 wenn x == 1 sonst .. " musst du bei den .. nur mit der allgemeinen Formel ergänzen und die Bedingung aus dem Zitat muss man mehr oder weniger glaubhaft begründen, nix ausrechnen

 

[BlackSalad]

Hey,

jetzt hab ich wieder das Problem, dass ich wieder nicht weiß wie ich die Terminierungsfunktion finden soll.
Ich blick da wohl scheinbar immer noch nicht durch.

Wenn ich diese Funktion habe:

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

wie komme ich da nun auf eine Terminierungsfunktion?

 

[SlaterB]

es gibt keinen einzigen wichtigen Unterschied zur vorherigen Frage, meine Antworten lauten zu 95% genauso,
mal dahingestellt ob du sie bisher verstanden hast oder sie gar korrekt sind

 

[Crowcrow]

Die Terminierungsfunktion für die letzte Funktion wäre doch f(n) = n, richtig? Ich versuche selbst gerade das Thema nochmal aufzufrischen.