[Scheme] Iterativ vs. rekursiv

[dasDull]

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?