# Recursions killing me

• 01-28-2008
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
• 01-28-2008
Dino
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 ; }```
• 01-28-2008
robatino
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).
• 01-28-2008
Dino
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
• 01-28-2008
robatino
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).
• 01-28-2008
brewbuck
Quote:

Originally Posted by Todd Burch
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.
• 01-28-2008
NeonBlack
The case of 100 is very famous, as according to legend was discovered by Gauss when he was very young (elementary school-aged).
• 01-28-2008
esbo
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.
• 01-28-2008
esbo
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; }```
• 01-28-2008
esbo
Mind you, recursion is a topic which crops up here again and again.
• 01-28-2008
Doodle77
esbo, any particular reason you use the old (i.e. pre-C89) function declaration syntax? TurboC?
• 01-28-2008
esbo
Quote:

Originally Posted by Doodle77
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; }```
• 01-29-2008
Elysia
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.