Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
aufgabe 10.4 iterativ nicht loesbar?
hi,
kann diese aufgabe ueberhaupt iterativ geloest werden?
hier meine rekursive loesung:
[CODE](define (square-list-rek list)
(if (null? list)
'()
(cons (* (car list) (car list))
(square-list-rek (cdr list)))))
(square-list-rek '(1 2 3 4 5))[/CODE]
die funktioniert wunderbar. ich frag mich bloss, ob das mit der gefragten “korrekten implementierung” gemeint ist.
gruss,
-steppenwolf
Ich habs auch nur rekursiv geschafft. Steht auch nicht da wie man es lösen soll, also kanns uns egal sein ! 
Hat es nicht mal geheißen dass man jede rekursive Funktion auch iterativ ausdrücken kann und umgekehrt?
Ich würde aber auch sagen dass es nicht iterativ geht, da die Listen in Scheme nun mal rekursiv definiert sind.
Hier eine iterative Lösung, geht mittels “reverse” :
[CODE](define (square-list x)
(define (iter list result)
(if (null? list)
result
(iter (cdr list)
(cons
(square (car list)) result ))))
(iter (reverse x) '()))
(define (square x)
(* x x ))[/CODE]
Japp, man kann jedes rekursive Problem auch iterativ Loesen!!!
Die erzeugten Prozesse sind ja beides mal rekursiv, nur die Art und Weise, wie wir die erzeugen, unterscheidet sich. Fuer den Computer ist das sowas wie schnurzbumbblbatcchpengegal.
ok, ein bischen spät 
aber ganz normales dings ohne reverse…
(define (square-list x)
(define (square x) (* x x))
(define (iter lst erg)
(cond ((null? lst) erg)
(else (iter (cdr lst) (append erg
(list (square (car lst))))))))
(iter x '()))also unser übleiter hat uns erklärt, dass ein “iterativer prozess” (wie wir ihn in scheme programmieren würden) zwar im prinzip so ähnlich wie rekursiv aussieht, nur dass eben genau diese art der rekursion (“endrekursion”, “tail recursion”) vom scheme-interpreter “besonders effizient”, eben iterativ, umgesetzt wird. es wird also auch intern nicht mehr speicher benötigt, weil das dann als eine art schleife ausgeführt wird. ähm… verstanden so?
das ergebnis is natürlich das gleiche… aber dem PC is das eigntlich wirklich nicht egal welche Form des Programms er ausführt. Iterative Versionen benötigen nämlich im Gegensatz zu ihren rekursiven version nur KONSTANTEN Platzbedarf und LINEAREN Zeitbedarf.
Rekrusive Programme können da schon anspruchsvoller sein (linearer Platzbedarf, linearer oder exponentieller Zeitbedarf…) :]
Es ist der Platzbedarf, der bei rekursiven Prozessen größer ist, weil immer ein unvollständiger Funktionsaufruf auf dem Stack bleibt.
Der Zeitbedarf ist genauso wie bei Endrekursion.
hmm… wie kommst du darauf? Bei der Fibonacci-Prozedur is das nicht so: Zeitbedarf ist bei der rekursiver Vraiante EXPONENTIELL, bei iterativer Version LINEAR
Fibonacci ist ja auch baumrekursiv, und außerdem ist der erhöhte Zeitbedarf dadurch zu erklären, dass für beide Summanden die ganze Kette ausgerechnet wird - die meisten Zahlen also 2mal.
Ich meinte Prozesse wie z.B. die Fakultätsberechnung (linear rekursiv). Da dauern beide Implementierungen gleich lang.