Ich will's mal versuchen. Bin zwar nicht mehr so ganz im Stoff, aber wir haben ja das
Skript. Auf Seite 7 steht ja, welche Eigenschaften rekursive und iterative Prozesse haben. (nachlesen!)
Wie sieht das in der Praxis in Scheme aus?
Das Standard-Beispiel: die Fakultätsfunktion.
|
Source code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
(define (fakr n)
(if (<= n 1)
1
(* n (fakr (- n 1)))
))
(define (faki n)
(define (iter p n)
(if (<= n 1)
p
(iter (* p n) (- n 1)))
)
(iter 1 n))
|
fakr ist die rekursive Variante der Fakultätsfunktion und faki die iterative.
Bei der rekursiven wird das Produkt rekursiv "zusammengebaut" - und dann erst berechnet. Für n = 7 ergibt sich:
(fakr 7)
(* 7 (fakr 6))
(* 7 6 (fakr 5))
(* 7 6 5 (fakr 4))
(* 7 6 5 4 (fakr 3))
(* 7 6 5 4 3 (fakr 2))
(* 7 6 5 4 3 2 (fakr 1))
(* 7 6 5 4 3 2 1)
Bei der iterativen Version wird ein Zwischenergebnis berechnet und dann an die Prozedur iter übergeben (jedenfalls ist das bei der applicative-order evaluation so).
Für n = 5 würde iter wie folgt aufgerufen:
Aufruf -> neues p, das an iter übergeben wird
(iter 1 5) -> (* 1 5)
(iter 5 4) -> (* 5 4)
(iter 20 3) -> (* 20 3)
(iter 60 2) -> (* 60 2)
(iter 120 1) Rückgabe von p an aufrufende Instanz (also faki)
Hoffentlich konnte ich dir damit etwas helfen.
migu
Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
Iterative Prozesse in Scheme
