Thread: 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

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 ; 
}

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

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

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

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.

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.

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

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