Recursions killing me

This is a discussion on Recursions killing me within the C Programming forums, part of the General Programming Boards category; Hi guys, I just can understand recursions! This is really putting me down. I've started quite good, and I perfectly ...

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

    Recursions killing me

    Hi guys,

    I just can understand recursions!
    This is really putting me down.
    I've started quite good, and I perfectly understand the following example:

    Code:
    void MyRecursion ( int n )
    {
        if (n<0)
       {
            printf("%d\n",n);
            MyRecursion(n-1);
       }
    }
    or

    Code:
    void MyRecursion ( int n )
    {
        if (n<0)
       {
            MyRecursion(n-1);
            printf("%d\n",n);
       }
    }
    But when there is a return value in the recursion I'm lost!
    for example:
    Code:
    int SumAll(int n)
    {
    	if (n>0)
    	{
    		return n+SumAll(n-1);
    	}
    	else
    		return 0;
    }
    I Couldn't find a single article that expalin this issue that an Idiot like me can actually understand.

    Anyone can point an article that will explain this issue for me please

    Many many thanks

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Try this:

    Code:
    #include <stdio.h> 
    
    int SumAll(int n) { 
    	int sum = 0 ; 
    	if (n > 0) { 
    		sum = SumAll(n-1) ; 
    	}
    	return sum+n ; 
    } 
    
    int main(void) { 
    
    	printf("The 'SumAll(5)' is %d\n", SumAll(5) ) ; 
    	return 0 ; 
    }

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    See

    http://en.wikipedia.org/wiki/Mathematical_induction

    Basically, to prove that SumAll(n) returns the sum of all integers from 1 to n for any n >= 0, you must show that

    1) SumAll(0) has the correct value (namely, 0).

    2) For any i > 0, if SumAll(i) has the correct value, then so does SumAll(i+1).

    Both of these follow from the recursive definition of SumAll(n).

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    This is interesting.

    SumAll(10) = 55
    SumAll(100) = 5050
    SumAll(1000) = 500500
    SumAll(10000) = 50005000

    (can you tell it's a slow day for me?)

    Todd

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    In general, SumAll(n) == n*(n+1)/2 (which can be proven by induction - check it for n == 0, then show that if it's true for any n >= 0, then it's true for n+1).

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by Todd Burch View Post
    This is interesting.
    Think that's weird? It works in any base.

    SumAll(0x10) = 0x88
    SumAll(0x100) = 0x8080
    SumAll(0x1000) = 0x800800
    etc...

    It's a basic consequence of the formula robatino mentioned.

  7. #7
    Registered User NeonBlack's Avatar
    Join Date
    Nov 2007
    Posts
    435
    The case of 100 is very famous, as according to legend was discovered by Gauss when he was very young (elementary school-aged).
    I copied it from the last program in which I passed a parameter, which would have been pre-1989 I guess. - esbo

  8. #8
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    I also hate recursion and avoid it like the plague, it's not very easy to follow.
    I would have done something like.
    Code:
    #include <stdio.h>
    main(){
    	printf("\n%d",SumAll(10));
    }
    SumAll(n)
    int n;{
    int result=0;
    	while(n>0){
    	    result+=n--;
    	}
    	return result;
    }
    I let my compiler decide what type the return value should be if I don't specify it, it
    usually gets it right. I seem to have ' got away with it' on this occasion anyway.
    I prefer to do it that way and avoid the problems of all this recursive 'nonsense'.
    Try debugging a recursive routine and you will see what I mean!!!!!
    It is effecively the same number of lines as Todd's example so I don't see the benefit
    of usinig recursion, and i dont have to worry about stack overflow either.

  9. #9
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Could of also done it like this, saves a line or two.
    Code:
    #include <stdio.h>
    main(){
    	printf("\n&#37;d",SumAll(10));
    }
    SumAll(n)
    int n;{
    int result=0;
    	while(n>0) result+=n--;
    	return result;
    }
    Last edited by esbo; 01-28-2008 at 08:36 PM.

  10. #10
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Mind you, recursion is a topic which crops up here again and again.

  11. #11
    Registered User
    Join Date
    Feb 2006
    Posts
    54
    esbo, any particular reason you use the old (i.e. pre-C89) function declaration syntax? TurboC?

  12. #12
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by Doodle77 View Post
    esbo, any particular reason you use the old (i.e. pre-C89) function declaration syntax? TurboC?
    Not really, I probably copied it from the last program in which I passed a parameter, which
    would have been pre-1989 I guess.
    Anyhow as it works I don't fix it.
    Actually I am using DJGPP or whatever it is called.
    I guess by avoiding passing parameter I also avoid the various problem which might
    occur when they change the syntax etc....
    Actually the code below also works, which looks neater, dunno why I did it like that before,
    but left to my own devices I just make the variable global rather than pass it usually.
    I guess I can't be bothered to look up the syntax, or fear some horrendous bug developing!! It's a subconscius thing!!
    Maybe I just looked it up somewhere when I had to pass a value and found an old example!
    Actually I think it was from when I once bought a book about C - lol.
    Was a long time ago!! (never read it (obviously)).
    Actually I bought it when I started a new job, I though I would leave it lying around on my desk so people
    thought I knew what I was doing - lol. Was a cheap book, probably out of date.



    Code:
    #include <stdio.h>
    main(){
    	printf("\n&#37;d",SumAll(10));
    }
    SumAll(int n)
    {
            int result=0;
    	while(n>0) result+=n--;
    	return result;
    }
    Last edited by esbo; 01-28-2008 at 09:20 PM.

  13. #13
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,538
    Code:
    int main(){
    	printf("\n&#37;d",SumAll(10));
    }
    int SumAll(int n)
    {
            int result=0;
    	while(n>0) result+=n--;
    	return result;
    }
    Still writing the same, stupid, idiotic code.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. what are RECURSIONS....???
    By ajayd in forum C Programming
    Replies: 4
    Last Post: 02-16-2008, 09:42 PM
  2. Bush vs. Kerry
    By jlou in forum A Brief History of Cprogramming.com
    Replies: 178
    Last Post: 11-29-2004, 02:45 PM
  3. Killing someones grandparents
    By nickname_changed in forum A Brief History of Cprogramming.com
    Replies: 37
    Last Post: 09-07-2003, 07:56 AM
  4. Recursions
    By incognito in forum C++ Programming
    Replies: 3
    Last Post: 11-27-2001, 07:12 PM
  5. Replies: 3
    Last Post: 11-17-2001, 08:16 AM

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