need help to understand the working of recursion in c

Question

#include<stdio.h>
#int add(int n);

int main()
{
    int n;
    printf("Enter an positive integer: ");
    scanf("%d",&n);
    printf("Sum = %d",add(n));
    return 0;
}

int add(int n)
{
    if(n!=0)
    return n+add(n-1);  /* recursive call */
}

How will this code executed without having a base case like if(n==0){return 0;}?

Why is the function type set with a `#` in front? – AntonH Apr 16 '14 at 15:28 — AntonH, Apr 16 '14 at 15:28

score 2 · Answer 1 · answered Apr 16 '14 at 15:28

2

Without a base case you are creating code with undefined behaviour. Your compiler will issue a warning saying that your function that returns int does not have a return statement. This does not mean that the function that called it won't look for a returned value which may or may not contain garbage.

answered Apr 16 '14 at 15:28

Sergey L.

21,822
5
49
75

3

That is because of luck, not because of design. – JohnH Apr 16 '14 at 15:47
@BOB: "Undefined behaviour" means "anything can happen". "Working fine" is "anything", as is "working fine on days with a full moon and emailing your passwords to Romania on days with a new moon". – Eric Lippert Apr 16 '14 at 20:47

score 0 · Answer 2 · answered Apr 16 '14 at 15:34

You're going to run into problems here: add will only return a value if n != 0, so if n <= 0, you won't have a value returned, so when add calls itself with n-1 passed in, you'll eventually reach your base case that doesn't exist, and bad things will happen.

score 0 · Answer 3 · answered Apr 16 '14 at 15:35

0

if(n==0){return 0;}

is the base case. The base case exists to get the recursion to stop. Without a base case you will just infinitely recurse until you possibly hit some kind of error. In your case it will start adding negative numbers.

answered Apr 16 '14 at 15:35

GriffinG

662
4
13

1

That's because you have if(n!=0) which causes the recursion to stop if n is 0. The only difference is you aren't specifying a return value so it has undefined behavior. In your case it works, but it's not guaranteed to work. http://stackoverflow.com/questions/4644860/function-returns-value-without-return-statement – GriffinG Apr 16 '14 at 15:44

score 0 · Answer 4 · edited May 23 '17 at 11:57

From the C standards:

Flowing off the end of a function is equivalent to a return with no value; this results in undefined behavior in a value-returning function.

Your compiler may warn you:

not all control paths return a value

It's the same situation with this one. This is calling convention and architecture dependent. The return value is the result of last expression evaluation, stored in the eax register. So when n==0, you function add() returns 0, but it's a result of undefined behavior.

need help to understand the working of recursion in c

4 Answers4