1. A recursive function has to call itself at some point.
2. Everything to be computed after that recursive call ---- we call this the continuation.

let rec sum n = if n = 0 then 0 else n + sum (n - 1)

3. Sometimes the continutation is empty

let rec isEven n = if n = 0 then true else if n = 1 then false else isEven (n - 2)

4. In general, to support recursive functions, we need a call stack

5. Functional programmers suddenly realized: If the continuation is empty,
   we don't need to push into the call stack. This optimization is called
   tail call optimization.

Q1. Can any function be turned into a tail recursive equivalent?

let sum n =
  let rec helper acc n = if n = 0 then acc
                         else helper (acc + n) (n - 1) in
  helper 0 n

----

let rec sum n = if n = 0 then 0 else n + sum (n - 1)

To calculate sum n:
-------------------
1. Check if n = 0
2. If so, then return 0
3. Otherwise:
   b. Let y = sum (n - 1)
   c. Return n + y

TODO
----
Let y''' = sum 7
Let y'' = 8 + y'''
Let y' = 9 + y''
Let y = 10 + y'
Return y

1. Calculate SUM ______________
2. ADD ________ to the previous value
3. RETURN ____________

Reify==="to make real"

type todoitem = CALLSUM of int | ADD of int

                             (*  vvv I promise that the return value is an int *)
let rec doer (l : todoitem list) (pot : int) : int =
             (* ^^^ I promise you that l is a value of type todoitem list *)
  match l with
  | CALLSUM n :: tl ->
      if n = 0 then doer tl pot
      else let newList = CALLSUM(n - 1) :: ADD n :: tl in
           doer newList pot
  | ADD n :: tl -> doer tl (n + pot)
  | [] -> pot

let tlsum n = doer [ CALLSUM n ] 0



Remove pot from shelf
Fill with water
Set pot on stove
Add pasta
Feed the cats