Thread: simple recursion question

I have the following code that sum all the numbers from 1 to N.

Code:

#include <stdio.h>

int Sum(int n)
{
	if (n>0)
	{
		return n+Sum(n-1);
	}
	else
		return 0;
}

int main(void)
{
	printf("%d\n",Sum(4));
	return 0;
}

I don't understand how it works...
Can someone please explain this code step by step.

Many Thanks!!!

Originally Posted by salvadoravi

I have the following code that sum all the numbers from 1 to N.

Code:

#include <stdio.h>

int Sum(int n)
{
   if (n>0)
	{
      printf("\n &#37;d", n);
		return n+Sum(n-1);
	}
	else
		return 0;
}

int main(void)
{
   char ch;
	printf("\n\n\n\n %d\n",Sum(4));
   printf("\n\n Press Enter to Exit ");
   ch = getchar();
   printf("%c", ch);
	return 0;

}
/*

I don't understand how it works...
Can someone please explain this code step by step.

Many Thanks!!!

Recursion can be thought of like a stack of plates.

Take a pen and some paper plates, and walk through the program.

1) It should print a value, but the value is a call to a function, so control jumps to the first command in Sum(n). With each function call, you're onto another paper plate.

2) N is checked against 0, and is true, so the if statement is executed.

3) and our first plate gets this written on it: return 4, and we make our second call to Sum(n). Put that plate on the table.

4) Control jumps to the top of Sum(), again. So get a new plate, and again, the if statement is evaluated to true (non-zero). We get to the return statement and the value for this plate is 3. Write that on the new plate, and put it right on top of the first paper plate.

The value Sum(n - 1) can't be arithmetically evaluated because that function call has not yet been made. The instant the call to Sum() is made, we're onto a new plate. It's not n + n - 1, that is left on the plates. It's just n.

5) Control jumps to the top of Sum(), again. So get a new plate, and again, the if statement is evaluated to true (non-zero). We get to the return statement and the value for this plate is 2. Write that on the new plate, and put it on the top of the paper plate stack.

As before, the call to Sum(n - 1) immediately tells you to reach for a new paper plate.

6) Control jumps to the top of Sum(), again. So get a new plate, and again, the if statement is evaluated to be true (non-zero). We get to the return statement and the value for this plate is 1. Write that value on the new plate, and put it on top of the paper plate stack.

As before the value of n is passed as a parameter to Sum, by copying a new n. So we have not one n, by now. We have one n for every single plate.

7) Control jumps to the top of Sum(), again. So get a new plate, and now, the if statement is evaluated to false. We get to the return statement AFTER the else, for the first time, and the value for this returned int is 0.

So write a zero on that plate and put it on top of our plate stack. Now we have all the plates stacked up in the right order, and we just Pop them off, one at a time, from the top.

Code:

Last plate:   0. Throw that plate away. Control moves to the NEW top plate you've just uncovered.
Fourth plate: 1  uncovering a 1.
Third plate:  2  etc.
Second plate: 3  
First plate:  4   (Bottom plate in the stack)
====================
Sum them up: 10

It's very helpful if you step through a recursive program, while watching
some variable values in a watch window.

Thank you guys great words!