Praktikum 12

1. Definieren Sie eine Prozedur doppelt, die eine Prozedur mit einem Argument als Argument hat und eine Prozedur als Ergebnis liefertm die die ursprüngliche Prozedur zweimal anwendet. Wenn zum Beispiel inc eine Prozedur ist, die 1 zu ihrem Argument addiert, dann sollte (doppelt inc) eine Prozedur sein, die 2 addiert. Welcher Wert wird geliefert von

   (((doppelt (doppelt doppelt)) inc) 5)

2. Ben Bitdiddle beschließt, eine Prozedur zu schreiben, die die Anzahl der Paare in einer beliebigen Listenstruktur zählt. "Das ist einfach", überlegt er. "Die Anzahl der Paare in einer beliebigen Listenstruktur ist die Anzahl im car-Teil plus die Anzahl im cdr-Teil plus eins für das aktuelle Paar." So schreibt Ben folgende Prozedur:

   (define (paar-zaehler x)
     (if (not (pair? x))
   	0
   	(+ (paar-zaehler (car x))
   	   (paar-zaehler (cdr x))
   	   1)))

   Zeigen Sie, daß diese Prozedur nicht korrekt ist. Zeichnen Sie insbesondere Kasten-Zeiger-Diagramme für Listenstrukturen, die aus genau drei Paaren bestehen, für die Bens Prozedur jedoch als Ergebnis 3, 4, 7 bzw. gar kein Ergebnis liefert.
3. Eine Funktion f ist definiert durch die Regel, daß f(n)=n, falls n<3 und f(n)=f(n-1)+2f(n-2)+3f(n-3), falls n>=3. Schreiben Sie eine Prozedur, die f in einem rekursiven Prozeß berechnet. Schreiben Sie eine Prozedur, die f in einem iterativen Prozeß berechnet.