[Scheme] Iterativ vs. rekursiv

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

Mit dem Begriff iterativ ist es so eine Sache. Üblicherweise bezeichnet iterativ ein Programm mit Schleifen anstatt Rekursion. Also gibt es eigentlich keine iterativen Programme in Scheme nach dieser Deutung der Begriffe, denn Scheme kennt keine Schleifen!

Alle von dir geposteten Funcktionen (außer die Hilfsfunktion fibz) sind rekursiv, d.h. sie rufen sich selbst auf.
Ja, die zweite von dir gepostete Version der Fibonacci-Zahlen ist auch rekursiv: fibi ruft erneut fibi auf. Der Unterschied ist lediglich in der Anzahl der rekursiven Aufrufe:
1. fibo ruft sich selbst zweimal auf. Da dies in jedem der n Schritte passiert hat man insgesamt exponentiell viele Aufrufe.
2. fibi ruft sich selbst nur einmal auf. Deswegen gibt es insgesamt nur n viele Aufrufe.

Den Unterschied zwischen iterativ und rekursiv (in der üblichen Verwendung der Begriffe) kann man besser an einer nicht rein funktionalen Sprache wie C verdeutlichen, wo es auch Schleifen als Alternative zur Rekursion gibt.
Hier wäre Fibonacci rekursiv (langsame Variante):

Code:

---

int fib(int n){
  if (n < 2) {
    return n;
  else {
    return fib(n-1) + fib(n-2)
  }
}

---

Fibonacci iterativ:

Code:

---

int fib(int n){
  int i = 0;
  int j = 1;
  for (int k = 0; k < n; ++k) {
    int temp = i + j;
    i = j;
    j = temp;
  }
  return i;
}

---

Diese Variante benutzt eine for-Schleife zum iterieren und ruft sich nicht selbst auf. Wie oben erwähnt geht das in Scheme gar nicht!

Das Beispiel der Fibonacci-Zahlen zeigt jedoch, dass es manchmal verschiedene Arten gibt, ein Problem durch Rekursion zu lösen, wobei diese sich in der Effizienz stark unterscheiden können. Die bessere fibi-Variante nennt man tail recursion(ein rekursiver Aufruf am Ende), und diese ist im Prinzip äquivalent zu einem Programm mit einer einfachen while-Schleife.
Bei dem ursprünglichen Listenprogramm ist die von dir gepostete Variante schon optimal. Man hat hier nicht das Problem wie bei fibo mit den exponentiell steigenden Aufrufen, da der rekursive Aufruf nur einmal stattfindet. Insofern ist dies schon die "iterative" Variante der Rekursion.

Im allgemeinen kann man natürlich nicht jede Rekursion so umschreiben, sodass nur ein Aufruf benötigt wird. Ein Beispiel wäre quicksort, wo eine Liste erst in zwei Hälften geteilt wird (eine mit den großen und eine mit den kleinen Elementen) und dann beide Hälften sortiert und aneinandergereiht werden.
Hier werden natürlich beide Aufrufe zwingend benötigt!
In einer Sprache wie C könnte man auch eine iterative Variante von quicksort schreiben, die nur Schleifen und keine Rekursion benutzt. Ist in dem Falle aber ziemlich hakelig, denn im Prinzip muss man dann den Callstack aus der Rekursion von Hand implementieren. Aber in diesem Sinne gilt, dass jedes rekursive Programm auch iterativ umgeschrieben werden kann.

Hoffe es hilft ein bisschen.

Edit: Ich glaube dein Programm fügt nicht ein x vor jedem y ein, sondern nur vor dem ersten y. Kann das sein?

Zitat:

---

Zitat von dasDull

Edit: Ich glaube dein Programm fügt nicht ein x vor jedem y ein, sondern nur vor dem ersten y. Kann das sein?

---

Da hast Du recht. Is mir gar nicht aufgefallen. Aber stimmt. Damit es bei jedem x ein y einschiebt, müsste man

Code:

---

(define (insertbefore3 x y ls)
  (cond
    ((null? ls) '())
    ((eq? (car ls) x)(cons (car ls)(insertbefore3 x y (cdr ls)))
    (else (cons (car ls)(insertbefore3 x y (cdr ls)))))))

---

Aber da wehrt sich das Programm grade dagegen.

Code:

---

else: not allowed as an expression in: (else (cons (car ls) (insertbefore3 x y (cdr ls))))

---

Kann auch sein, dass es einfach schon zu spät ist.