Recursion functions in C

Question

So below is my code, I'm having some difficulties trying to put my knowledge on recursion functions into use. My program wants to find the sum all the natural numbers, using the users input as the last number.

I have tried to use a recursion function but it doesn't seem to work. In my eyes the problem is that once function calls its self again the integer total doesn't seem to remember it's initial value. Can someone please help me out.

include <stdio.h>

int sum(int); 

main(){
    int a; 
    printf("Enter your number\n");
    scanf_s("%d", &a); 
    printf("The answer is %d", sum(a)); 
    getch();
}

int sum(int a){ 
    int total = 0;
    total = total + a;  /*add the new value of a*/
    a--;    /*decrease the value of a by one*/
    if (a == 0){
        return total;   /* leave the function and display this value */
    }
    else {
        sum(a); /*call this function again */
    }
}

Answer 1

Let's write a definition of the sum() function in words:

The sum of all natural numbers up to n is n plus the sum of the natural numbers up to n-1.

Notice that this definition is recursive because I need to calculate the sum for a smaller number in order to calculate the sum for a given number. Using this as a guide, we might try something like this:

int sum(int n) {
    return n + sum(n - 1);
}

If you try to run this with some test code, you will get a stackoverflow. This is because we have not given a base case to tell when the iteration stops. This base case is implicit in our definition above. The smallest natural number is zero. We are simulating natural numbers with the int type which stores integers. So we need to modify our code slightly to make sure we do not allow negative integers:

int sum(int n) {
    if (n <= 0)
        return 0;

    return n + sum(n - 1);
}

I think part of the problem you are encountering is that you want to use an accumulator. Often with recursive solutions this is not necessary since the recursive call can immediately return the accumulated value.

Analysis:

Let's take a look at how this works with an example:

void main() {
    int x = sum(3);

    printf("%d\n", x);
}

Level 1

The first line calls sum() and sets n to 3.

int sum(int n) {
    if (n <= 0)

n is not less than or equal to zero, so we skip to the return

        return 0;

    return n + sum(n - 1)

Now we call sum() again with a value of n-1 which is 2

}

Level 2

Now sum() is evaluated with n set to 2.

int sum(int n) {
    if (n <= 0)

Again we skip the if statement.

        return 0;

    return n + sum(n - 1);

And sum() is called with a value of 1.

}

Level 3

int sum(int n) {
    if (n <= 0)

Since n is 1, we skip the if.

        return 0;

    return n + sum(n - 1);

Now we call sum(0).

}

Level 4

int sum(int n) {
    if (n <= 0)
        return 0;

Since n is 0, we return 0. This sends execution back to

Level 3

    return n + sum(n - 1);

On this level n is 1 and Level 4 returned a value of 0. Adding these together and we return a value of 1 back to Level 2.

Level 2

    return n + sum(n - 1);

On this level n is 2 and Level 3 returned a value of 1. Adding these together and we return a value of 3 back to Level 1.

Level 1

    return n + sum(n - 1);

On this level n is 3 and Level 2 returned a value of 3. Adding these together and we return a value of 6 back to main().

    printf("%d\n", x);

Finally, main() prints the value of x which was set to 6.

Answer 2

You have two problems.

First, every time you call the function, you're initializing the local variable total to 0. So it's not calculating a total across all the calls, it starts from 0 every time you make the recursive call. You need to pass the total as an argument, so that you can add to it.

Second, when you make the recursive calls, you're not doing anything with the result that it returns. You need to return its value back up the chain.

include

int sum(int, int); 

main(){
    int a; 
    printf("Enter your number\n");
    scanf_s("%d", &a); 
    printf("The answer is %d", sum(a, 0)); 
    getch();
}

int sum(int a, int total){ 
    total = total + a;  /*add the new value of a*/
    a--;    /*decrease the value of a by one*/
    if (a == 0){
        return total;   /* leave the function and display this value */
    }
    else {
        return sum(a, total); /*call this function again */
    }
}

Answer 3

If you intend to add the values you should do it somewhere, try

int
sum(int n)
{
    if (n == 0)
        return n;
    return n + sum(n - 1); // Add the current value to the sum of the values
                           // from n - 1 to 0.
}

Your function also, causes infinite recursion because you always pass a to the sum() function so a == 0 would be only true if you start with n == 0.