I am trying to understand how this works. My instructor is teaching his first class, in summer on top of that, and only had 3 slides on this and had to rush over it. His example is:
Give a recursion algorithm for computing 0+1+2+...+n, where n is non-negative
His answer is
procedure add(n: nonnegative integer)
if n = 0 then return 0
else return n + (n - 1)
He says the output is 0+1+2+...+n but how? If you use n + (n - 1) and input 2, you would have 3, and if you input 3, you would have 5. If you continue with 4, you end up with 7. So it seems to be jumping by 2, not 1. What am I not understanding?
The idea of recursion is to break down a big task into similar, smaller tasks. This can be imagined as delegating a task to an assistant (who may have his own assistant, and so on).
Imagine you are supposed to add the numbers from 1 to 100. Instead of adding them all yourself, you ask your assistant to add the numbers from 1 to 99. You wait, (he asks his assistant for the sum from 1 to 98, etc.) and eventually he gives you an answer: 4950. Then you add 100 to that to get 5050 for the final result.
The program you give (when corrected) implements this behavior: If $n$ is 0, there is no way to make the task simpler, so it just returns 0. Otherwise we ask for the result of the problem for $n-1$ (which is what "add(n - 1)" gives) and then add on $n$ to get the correct total.