Praktikum 2

1. Kann man "if" als gewöhnliche Prozedur mit Hilfe von "cond" definieren, anstatt es als Sonderform zu behandeln? Betrachten Sie z. B. folgenden Versuch:
   

   (define (neues-if praedikat then-klausel else-klausel)
     (cond (praedikat then-klausel)
           (else else-klausel)))

   Wie reagiert der Interpretierer auf die Ausdrücke

   (neues-if (= 2 3) 0 5)

   und

   (neues-if (= 1 1) 0 5)

   ? Was passiert, wenn Sie diese Prozedur anstelle von "if" in der Prozedur "wurzel-iter" aus der Vorlesung verwenden? Geben Sie eine genaue Erklärung!
2. Die Fibonacci-Zahlen sind definiert als
   

                 0                  falls n = 0
   Fib(n) =      1                  falls n = 1
                 Fib(n-1)+Fib(n-2)  sonst

   1. Setzen Sie diese Definition um in eine rekursive Prozedur, die Fib(n) berechnet.
   2. Formulieren Sie eine iterative Variante nach folgender Idee:

      Initialisiere a = 1, b = 0.
      Wiederhole gleichzeitig die Transformationen (a = a + b, b = a) n-mal.

   Hinweis: Die Variablen a bzw. b sind Parameter in einer Hilfsprozedur "fib-iter"; (fib n) wird dann berechnet als (fib-iter 1 0 n).
   3. Wie sieht das Laufzeitverhalten von 1. gegen 2. bei Erhöhung des Arguments n um eins aus, wie bei Verdopplung von n? Allgemeine Formel?
3. Die in der Vorlesung angegebene Prozedur "summe" erzeugt eine lineare Rekursion. Die Prozedur kann so umgeschrieben werden, daß die Summe iterativ berechnet wird. Zeigen Sie dies, indem Sie die fehlenden Ausdrücke in der folgenden Definition ergänzen:
   

   (define (summe term a naechstes b)
     (define (iter a ergebnis)
       (if <??>
           <??>
           (iter <??> <??>)))
     (iter <??> <??>))