Lösungen Blatt2 :

Zu Aufgabe 1:

Zu Aufgabe 2:

Zu Aufgabe 3:

(*Rekursive Lösung *)
fun fib (x) = if (x<=1) then x else fib(x-1)+fib(x-2);

(*iterative Lösung:*)
fun fibIt (n,a,b) = if(n<=0) then a else fibIt(n-1,b,a+b);
fun fibIter (N) = fibIt (N,0,1);
(* Die Iteration ist eine Spezialform der Rekursion, bei der kein Stack für die rekursiven Funktionsaufrufe gebraucht wird. *)

(* Es wurden auch imperative Verisonen abgegeben bei denen die while-Konstruktionen von ML genutzt wurden. Diese gehackten Programme sind an sich korrekt, ziehen aber Nachteile des imperativen Programmierens nach sich (Korrektheit???). *)

(*Die imperative Version*)
fun fibiter n = let val result0 = ref 0
val result1 = ref 1
val z = ref 0
val hilf = ref 0

(* Es wurden 4 lokale Variablen deklariert,wobei hilf, -wie aus dem folgenden Programmteil ersichtlich- als Hilfs- variable dient ,result1 die jeweils auf result0 folgende Fibonaccizahl bezeichnet und z als Laufvariable dient*)

in while !z < n do (z := !z + 1;
hilf := !result0;
result0 := !result1;
result1 := !result1 + !hilf);
!result0
end;

Zu Aufgabe 4:

(*Hilfsfunktion mit zusätzlichem argument*)
fun f2 ( x,n)= if x<=n then x else f2(x-n,n+1);

fun f x = f2(x,1);