1. ## 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. 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. 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. 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. 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. 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.

7. The case of 100 is very famous, as according to legend was discovered by Gauss when he was very young (elementary school-aged).

8. 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. 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;
}```

10. Mind you, recursion is a topic which crops up here again and again.

11. esbo, any particular reason you use the old (i.e. pre-C89) function declaration syntax? TurboC?

12. 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;
}```

13. 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.