simple recursion question

This is a discussion on simple recursion question within the C Programming forums, part of the General Programming Boards category; I have the following code that sum all the numbers from 1 to N. Code: #include <stdio.h> int Sum(int n) ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    84

    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!!!

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Well.... Sounds like you're stuck on recursion. I wrote a post on this subject earlier:

    Recursion UGH!

    The original topic:

    Recursion UGH!

    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.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    Perhaps
    Code:
    #include <stdio.h>
    
    int Sum(int n)
    {
    	if (n>0)
    	{
    		int newSum;
    		printf("--Getting closer, currently at &#37;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;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by salvadoravi View Post
    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.

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    84
    Thank you guys great words!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple question regarding variables
    By Flakster in forum C++ Programming
    Replies: 10
    Last Post: 05-18-2005, 08:10 PM
  2. Simple class question
    By 99atlantic in forum C++ Programming
    Replies: 6
    Last Post: 04-20-2005, 11:41 PM
  3. Simple question about pausing program
    By Noid in forum C Programming
    Replies: 14
    Last Post: 04-02-2005, 08:46 AM
  4. simple question.
    By InvariantLoop in forum Windows Programming
    Replies: 4
    Last Post: 01-31-2005, 11:15 AM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21