Welche Art der Rekursion?

[Neppo]

Ich schreibe nächste Woche eine Klausur in GdI (Grundlagen der Informatik).
Ich versuche gerade das Thema "Rekursionen" zu verständlichen.

Wir haben folgende Arten der Rekursion durchgenommen:
- Primitive Rekursion
- Endrekursion
- Lineare Rekursion
- Allgemeine Rekursion
- Wechselseitige Rekursion


Nun eine Frage (vielleicht kann mir diese jemand beantworten):
Welche Art der Rekursion sind die Fibonacci-Zahlen?

Die Fibonacci-Zahlen sind rekursiv definiert durch
f(0) = 1
f(1) = 1
f = f(n-1) + f(n-2)

Ich kann dafür die Wechselseitige Rekursion (ist ja nur eine Methode) und die Lineare Rekursion (da ja die Rekursion mehr als 1x auftritt) ausschließen.
Ist dies vielleicht eine Endrekursion?

 

[fluessig]

Vielleicht nennst du die Definitionen auch noch zu den anderen Begriffen. Ich weiß gar nicht, ob in meinen GdI Unterlagen so fein unterschieden wurde.

 

[Neppo]

In meinem Script-Buch des Professors sind die Arten folgendermaßen definiert (wobei ich mit diesen Definitionen recht wenig anfangen kann):

Primitive Rekursion:
f = g, falls P
h(n, f(pred ()), sonst

dabei ist h eine Funktion h : N0 x R -> R.

Endrekursion:
f = g, falls P
f(r)), sonst

dabei ist r eine Funktion r : N0 -> N0

Linieare Rekursion:
f = g, falls P
h(n, f(r)), sonst

Dieser Fall verallgemeinert die primitive Rekursion und die allgemeine Rekursion.

Allgemeine Rekursion:
Dies ist der allgemeinste Fall. Hier können wir keine engere Definition vergeben.



Die kurzen "umgangssprachlichen" Definitionen oben, habe ich mir aus dem Netz gefischt, um es überhaupt zu verstehen.
Falls jemand einen guten Link zu Beschreibungen der Arten noch hat, bitte posten!

 

[Thomas Darimont]

Hallo!

Die Fibonaccifunktion ist nichtlinear rekursiv .

"Eine rekursive Funktion heisst nichtlinear rekursiv, wenn die Ausführung der Funktion zu mehr als einem rekursiven Aufruf führt."

Gruß Tom

 

[Neppo]

OK - Danke Thomas!

Noch eine Abschlussfrage:
Was sind so die Haupteigenschaften einer Primitiven Rekursion?

 

[Thomas Darimont]

Hallo!

-intuitiv berechenbar
-Turing berechenbar
-Stimmt mit der Klasse aller durch Schleifen berechenbaren Funktionen überein.
(NUR for und keine while oder goto's)
-what else ?

Gruß Tom

 

[RedWing]

Man kann die Fibbonacci Zahlen aber linear rekursiv umwandeln,
und erreicht somit eine Komplexität die in O liegt
Stichwort hierzu "tail recursion"...

Gruß

RedWing