Printable View
I have the following code that sum all the numbers from 1 to N.
I don't understand how it works...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;
}
Can someone please explain this code step by step.
Many Thanks!!!
Well.... Sounds like you're stuck on recursion. I wrote a post on this subject earlier:
http://cboard.cprogramming.com/showp...12&postcount=7
The original topic:
http://cboard.cprogramming.com/showthread.php?t=96161
Basically, the sum of 5, 4, 3, 2, 1 is the same as 5 + the sum of 4, 3, 2, 1. So that's all the function is doing.
Perhaps
Code:#include <stdio.h>
int Sum(int n)
{
if (n>0)
{
int newSum;
printf("--Getting closer, currently at %d\n", n );
newSum = n+Sum(n-1);
printf("--Getting closer new partial sum=%d\n", newSum );
return newSum;
}
else {
printf("--End of the line, returning 0\n" );
return 0;
}
}
int main(void)
{
printf("%d\n",Sum(4));
return 0;
}
Recursion can be thought of like a stack of plates.Quote:
Originally Posted by salvadoravi
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.
It's very helpful if you step through a recursive program, while watchingCode:
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
some variable values in a watch window.
Thank you guys great words!