Ich habe mal ne Frage zu den verschiedenen Rekursionsarten. Es gibt ja linear rekursive, baumrekursive und endrekursive. Und eine linear rekursive kann auch zu gleich endrekuriv sein, oder? Kann eine baumrekursive auch endrekursiv sein?
Dann habe ich in SICP diesbezüglich auch was von "Iteration" gelesen. Das sieht für mich endrekursiv aus, oder hab ich da was falsch verstanden?
Weiß jemand, ob und wo genaue Definitionen und Erkennungsmerkmale zu den Rekursionsarten im Skript stehen?
Ich habe versucht die Rekursionen (so wie ich das Skript interpetiere) zusammenzufassen:
Lineare Rekursion - Skript Seite 166
Der rekursive Aufruf wird in jeder Fallunterscheidung nur einmal verwendet.
Endrekursion - Skript 179
Das Ergebnis der Rekursion muss nicht mehr verknüpft/ weitergegeben werden.
Baumrekursion - Seite 180
Wenn eine Fallunterscheidung zu mehr als einem rekursiven Aufruf führen.
Endrek.: Ist das nicht ein Spezialfall der linearen Rekursion? Würde ich so sehen. Jedenfalls trifft das Kriterium, das du für lin. Rek. gegeben hattest, auch für Endrekursion zu.
Man kann doch jede linear rekursive Funktion endrekursiv machen, oder? Aus Performancegründen muss das ja eigentlich auch eine Voraussetzung sein …
Wenn ich mir jedoch zum Beispiel die Definition von filter im Skript (Slide 187) oder in den tools ansehe, dann ist die doch nicht endrekursiv. Dann wäre doch jede Funktion, die darauf aufbaut auch nicht endrekursiv und damit auch ineffizient. Oder macht der Kompiler die automatisch endrekursiv? Dann bräuchte man sich ja gar nicht mehr mit diesem Thema zu beschäftigen …
high
Lineare Rekursion - Skript Seite 166
Der rekursive Aufruf wird in jeder Fallunterscheidung nur einmal verwendet.
Endrekursion - Skript 179
Das Ergebnis der Rekursion muss nicht mehr verknüpft/ weitergegeben werden.
Baumrekursion - Seite 180
Wenn eine Fallunterscheidung zu mehr als einem rekursiven Aufruf führen.
lineare Rek.
das ergebnis der rek wird weiterverknuepft
bsp
(else
(cons (car xs)(blah x (cdr xs)
endrek
das ergebnis der rek wird nicht verknuepft.
bsp
(else
(blech (cdr xs) x)
baumrek
das ergebnis aus 2 rekursionen wird miteinander verknuepft
bsp
fibonachi zahlen
(+ (fib (- 1 n))
(fib (- 2 n)))
verschraenkte rek
die rekursionen rufen sich gegenseitig auf
bsp
ackermann funktion (acker x y)
(else
(a (- x 1)(a x (- y 1)))
christian
das filter als standartfunktion in tools.scm nicht endrekursiv ist, ist eine frechheit,
alle ab sofort meine verwenden [img]
http://images.rapidforum.com/images/i7.gif[/img]:
(define (filter_acc p? xs ys)
(cond ((null? xs) (reverse ys))
((p? (car xs)) (filter_acc p? (cdr xs) (cons (car xs) ys)))
(else (filter_acc p? (cdr xs) ys))))
(define (endfilter p? xs) (filter_acc p? xs '()))
@spacelord: wenn man eine funktion als linear oder sonstwie rekursiv einordnet, müssten die darin verwendeten funktionen egal sein, es geht wohl nur um die struktur der funktion selber,
wer weiss schon, wie plus und minus genau definiert sind, hoffentlich effizient…,
Lustig finde ich, daß wir im Scheme-Teil lernen und definieren, was Rekursion ist, nachdem in Prolog dieses Wissen (naja, die Fähigkeit zur Anwendung) schon vorausgesetzt wurde.
