Recursion help please

Understanding recursion is a pretty common problem, and its probably covered better elsewhere, but I'll mention some things you might just be learning, though I might be oversimplifying things - sorry if that's the case.

You probably know what a stack is by now, storage that you can add values and get them back most recent first, as in:

s.push(1); s.push(3); s.push(2); a = s.pop(); // a now has 2 b = s.pop(); // b now has 3

Function or method calls use a stack for all variables, including parameters. so if you have a function:

int f(int x) { int y; ... }

`x`, `y`, and space for a return value are put on the stack when you call it - grouped together it's called a frame. Each function call has a frame put on a stack, Stack frames include parameters - they are copies of the values passed in, so if a function changes it, the original is not affected.

Variables can refer to things (objects, records, structs) stored elsewhere. If you change something in that, there is only one copy that changes, but there are many references to it - not important for recursion though.

When you call a function, it obviously returns to the place it was called and then continues:

inf f(int x) { int y, r; y = g(x); r = h(y); return r; }

`f()`, `g()`, and `h()` have their own stack frames, after `f()` calls `g()`, it calls `h()`. There's nothing stopping `f()` from calling `f()`, because each call puts a new stack frame, so there is a copy of all variables and parameters for each call. Unfortunately, `f()` will call `f()` again and never stop until memory runs out.

To prevent this you need to indicate when `f()` should stop, and that's usually a parameter that must change each call. An example:

void f(int x) { g(x); if (x > 0) { f(x-1); } h(x); }

In this case `f()` calls `g()`, then `f()`, then `h()`, except that each call to `f()` has a smaller value for `x` so when it reaches 0 it won't call itself again. And it won't call `h()` until `f()` returns, which won't happen until `f()` reaches the bottom, then returns - each return will call `h()`, then return, which will then call that `h()`, until the last one returns. It will look like:

g() g() g() ...until x is 0 h() h() h()

If you understand all that, you should be able to do your assignment.