Hallo,

ein befreundeter Student braucht Hilfe mit einer schlecht lösbaren - wie er sie nennt - "Denksportaufgabe". Er hat mich gefragt, weil ich ebenfalls mal eine Zeit lang mit Scheme, Ruby und Python gearbeitet habe. Ich bin aber eben so ratlos wie er. Er braucht das für die Uni. Angeblich ist es was ganz Grundlegendes:

Es geht darum, in Scheme ein Skript zu schreiben, das in einer Liste ein bestimmtes Element sucht und vor dieses dann ein weiteres Element einfügt, also quasi:

Code: 
(insertbefore 2 3 '(1 2 3 4 5 6)
(In diesem Fall möchte er eine 3 vor jede 2 einfügen). Das Ergebnis wäre:
Code: 
(1 3 2 3 4 5 6)
Ja gut, ist nicht so schwer. Rekursion heißt das Zauberwort und Scheme lebt ja von Rekursion, also dass die Funktionen mit sich selbst verschachtelt werden können. Also wäre die naheliegende Lösung diese hier:

Code: 
(define (insertbefore x y ls)
  (cond
    ((null? ls) '())
    ((eq? (car ls) x)(cons y ls))
    (else (cons (car ls)(insertbefore x y (cdr ls))))))
Das führt also zu den Ergebnissen. Das Problem: Diese Funktion ist rekursiv. Das heißt sie bindet sich selbst in ihre Rechenoperation ein und verschachtelt sich soweit, bis die Liste durch ist. Angeblich gibt es die Möglichkeit, die Funktion auch ITERATIV(!) auszufertigen. Das bedeutet, man kann sie, leider nur sehr kompliziert umschreiben, sodass sie die Rechenoperationen über eine Variable und Hilfsfunktion hintereinander ausführt. Allerdings kennt mein Kumpel nur die Befehle: =, not, +, -, *, /, #t, #f, null?, eq?, define, lambda, cons, cond (else), if, car und cdr. Er kent nicht mal die Appendfunktion, um weitere Listen zu schreiben. Klar kann er sich die Appendfunktion selbst definieren, aber das ganze würde Ewigkeiten dauern.

Daher: Gibt es einen findigen Programmierer unter Euch, der diese Funktion auf iterativ umschreiben kann? Ich meine, es ist zwar ziemlich sinnlos, da es die Rechenschritte kaum reduziert. Aber laut seinem Professor kann man alles rekursive auf iterativ umschreiben. Ich bringe es nicht hin. Daher die Frage an Euch. Bei den Fibonaccizahlen schaffe ich es noch:

Fibonacci rekursiv:
Code: 
(define (fibo n)
  (if (< n 2)
      n
      (+ (fibo (- n 1))(fibo (- n 2)))))
Fibonacci iterativ:
Code: 
(define (fibz n)
  (fibi 0 1 n))

(define (fibi vv v n)
  (if (< n 2)
      v
      (fibi v (+ vv v)(- n 1))))
Natürlich muss man bei der iterativen Variante zwei Funktionen definieren. Aber bei den Fibonaccizahlen ergibt das auch wirklich Sinn. Denn bei der rekrusiven Version macht der Rechner bei der Fibonaccizahl n=40 schon schlapp (weil die Anzahl der Rechenschritte durch die Verschachtelung exponentiell ansteigen). Die iterative Version ermöglicht n = zehnstellig ohne weiteres.

Aber bei dieser Insertleft-Gleichung bringt es eigentlich kaum Benefit. Dennoch wäre es super, wenn er die Aufgabe lösen könnte. Weiß jemand von Euch, wie man das anstellt?

Viele Grüße,
Cuzco