Somebody please explain the algorithm in this problem for OCaml.
I have the solution but I do not understand it.
Define iterup: (int * 𝛼 → 𝛼) → int → int → 𝛼 → 𝛼. Iterup takes a function which receives the current number and the accumulator. It increments the counter number from a given start to a given end and applies the function each time. The last argument is the start value of the accumulator.
The solution is
let rec iterup f st ed acc =
if st > ed then
acc
else
iterup f (st+1) ed (f st acc)
What I do not understand is why we take in both n and s as arguments to f in the last part (f n s). What does that get us to when we talk in terms of tail recursion.
The last argument provides an accumulator which is a very idiomatic way to achieve tail recursion in OCaml. The function provided via the f argument provides a way to update that accumulator.
With an accumulator, we can build up the end state from our function as we go and pass it along to the next recursive call. Because each call no longer needs to access any state from previous calls, the stack space for each previous call can be re-used.
Every path in a recursive function either needs to be an exit from the recursion, or an update to the state passed to the function. Without at least one of each, we get stuck in unbounded recursion: an infinite loop.
Let's look at a call of iterup.
iterup (fun a b -> a + b) 1 5 0
iterup (fun a b -> a + b) 2 5 (0 + 1)
iterup (fun a b -> a + b) 3 5 (1 + 2)
iterup (fun a b -> a + b) 4 5 (3 + 3)
iterup (fun a b -> a + b) 5 5 (6 + 4)
iterup (fun a b -> a + b) 6 5 (10 + 5)
15
At no point do we have to work our way back up the call stack to find the solution, so the stack space used can be optimized to be constant.