iterative and recursive process
recall that
- a procedure generates a process when it is applied
- an iterative process uses constant space: it does work incrementally
- a recursive process grows then shrinks: it defers work
question: how can we ensure that the recursion ‘bottoms out”?
- recursive call must be on a smaller problem
- what makes a problem smaller?
we can choose!
must show that, whatever our notion, it can’t get smaller for ever