I gave you some "mis-information" in the lectures (I screwed up!!), when I was presenting material to show that we could implement "iteration" with "recursion". I (wrongly) implied that the recursive implementation of sum_to_n would require space of the order O(n) (that is if some procedural language required space for i and sum_n, the ml implementation would require space for n copies of i and sum_n). This is wrong! ______________________________________________________________________ fun do_while test body s = if test s then do_while test body (body s) else s; fun sum_body ((sum:int),(n:int)) = (sum+n,n-1) fun sum_test (_,(n:int)) = n > 0; fun sum_to_n (n:int) = do_while sum_test sum_body (0,n); ________________________________________________________________________ I implied that a call to "sum_to_n 5" would result in the following: (sum_body(sum_body(sum_body(sum_body(sum_body (0,5)))))) and would therefore have 5 function calls stacked up. This is not so. Things will proceed as follows: (0) sum_to_n 5 calls "do_while" (1) sum_test(0,5) delivers the result "true" (2) "sum_body(0,5)" will be evaluated, delivering the tuple (5,4). ^^^^ ^^ ^^^^^^^^^ (3) and then a recursive call is made to "do_while sum_test sum_body (5,4) Therefore, the recursive sum_to_n requires space only for "sum" and "n". The only criticsm that we can make, is that rather than "loop" back (as in a procedural language such as pascal) it makes a recursive call. Therefore, it incurs the overhead of "n" recursive function calls, whereas we would expect the procedural language's loop (FOR, DO, WHILE, what ever) statement (pascal?) to compile down to a IF with a (forgive me for this blasphemous statement) GOTO. But .... a clever "compiler" will recognise "tail recursion" (last call within function is a call to itself) and will map this into iteration (I feel cheated. Do you?). Note "compiler". Generally, we use ml as an interpreter, and this will just go ahead and make that call. Sorry about the mistake.