sum of N natural Number Using Recursion in c

Question

#include<conio.h>
#include<math.h>
int sum(int n);
int main()
{

    printf("sum is %d", sum(5));
    return 0;

}
//recursive function
int sum(int n)
{
    if(n==1)
    {
        return 1;
    }
   int sumNm1=sum(n-1); //sum of 1 to n
   int sumN=sumNm1+n;
}

Here i didn't understand how this code works when n==1 becomes true, How this code backtracks itself afterwards..?

Answer 1

Like pointed in comments, the problem is that you don't return the value you compute from within the function (Undefined Behavior). You calculate it correctly (but in a clumsy way, using 2 unneeded variables).
If you add a return sumN; statement at the end of the function, things should be fine.

Also, the type chosen for the return value is not the best one. You should choose:

• An unsigned type (as we are talking about natural numbers), otherwise half of its interval would be simply wasted (on negative values - which won't be used)

• One that's as large as possible (uint64_t). Note that this only allows larger values to be computed, but does not eliminate the possibility of an overflow, so you should also be careful when choosing the input type (uint32_t)

More details on recursion: [Wikipedia]: Recursion (it also contains an example very close to yours: factorial).

I've prepared an example.

main00.c:

#include <stdint.h>
#include <stdio.h>

#if defined(_WIN32)
#  define PC064U_FMT "%llu"
#  define PC064UX_FMT "0x%016llX"
#else
#  define PC064U_FMT "%lu"
#  define PC064UX_FMT "0x%016lX"
#endif


uint64_t sum(uint32_t n)  // Just 3 lines of code
{
    if (n < 2)
        return n;
    return n + sum(n - 1);
}


uint64_t sum_gauss(uint32_t n)
{
    if (n == (uint32_t)-1)
        return (uint64_t)(n - 1) / 2 * n + n;
    return n % 2 ? (uint64_t)(n + 1) / 2 * n : (uint64_t)n / 2 * (n + 1);
}


uint64_t sum_acc(uint32_t n, uint64_t acc)
{
    if (n == 0)
        return acc;
    return sum_acc(n - 1, acc + n);
}


int main()
{
    uint32_t numbers[] = { 0, 1, 2, 3, 5, 10, 254, 255, 1000, 100000, (uint32_t)-2, (uint32_t)-1 };
    for (size_t i = 0; i < sizeof(numbers) / sizeof(numbers[0]); ++i) {
        uint64_t res = sum_gauss(numbers[i]);
        printf("\nsum_gauss(%u): "PC064U_FMT" ("PC064UX_FMT")\n", numbers[i], res, res);
        res = sum_acc(numbers[i], 0);
        printf("  sum_acc(%u): "PC064U_FMT" ("PC064UX_FMT")\n", numbers[i], res, res);
        res = sum(numbers[i]);
        printf("      sum(%u): "PC064U_FMT" ("PC064UX_FMT")\n", numbers[i], res, res);
    }
    printf("\nDone.\n\n");
    return 0;
}

Notes:

• I added Gauss's formula (sum_gauss) to calculate the same thing using just simple arithmetic operations (and thus is waaay faster)

• Another thing about recursion: although it's a nice technique (very useful for learning), it's not so practical (because each function call eats up stack), and if function calls itself many times, the stack will eventually run out (StackOverflow). A recurrent call can be worked around that using an optimization - with the help of an accumulator (check [Wikipedia]: Tail call or [SO]: What is tail call optimization?). I added sum_acc to illustrate this

• Didn't consider necessary to also add the iterative variant (as it would only be a simple for loop)

Output:

(qaic-env) [cfati@cfati-5510-0:/mnt/e/Work/Dev/StackOverflow/q074798666]> ~/sopr.sh
### Set shorter prompt to better fit when pasted in StackOverflow (or other) pages ###

[064bit prompt]> ls
main00.c  vs2022
[064bit prompt]> gcc -O2 -o exe main00.c
[064bit prompt]> ./exe

sum_gauss(0): 0 (0x0000000000000000)
  sum_acc(0): 0 (0x0000000000000000)
      sum(0): 0 (0x0000000000000000)

sum_gauss(1): 1 (0x0000000000000001)
  sum_acc(1): 1 (0x0000000000000001)
      sum(1): 1 (0x0000000000000001)

sum_gauss(2): 3 (0x0000000000000003)
  sum_acc(2): 3 (0x0000000000000003)
      sum(2): 3 (0x0000000000000003)

sum_gauss(3): 6 (0x0000000000000006)
  sum_acc(3): 6 (0x0000000000000006)
      sum(3): 6 (0x0000000000000006)

sum_gauss(5): 15 (0x000000000000000F)
  sum_acc(5): 15 (0x000000000000000F)
      sum(5): 15 (0x000000000000000F)

sum_gauss(10): 55 (0x0000000000000037)
  sum_acc(10): 55 (0x0000000000000037)
      sum(10): 55 (0x0000000000000037)

sum_gauss(254): 32385 (0x0000000000007E81)
  sum_acc(254): 32385 (0x0000000000007E81)
      sum(254): 32385 (0x0000000000007E81)

sum_gauss(255): 32640 (0x0000000000007F80)
  sum_acc(255): 32640 (0x0000000000007F80)
      sum(255): 32640 (0x0000000000007F80)

sum_gauss(1000): 500500 (0x000000000007A314)
  sum_acc(1000): 500500 (0x000000000007A314)
      sum(1000): 500500 (0x000000000007A314)

sum_gauss(100000): 5000050000 (0x000000012A06B550)
  sum_acc(100000): 5000050000 (0x000000012A06B550)
      sum(100000): 5000050000 (0x000000012A06B550)

sum_gauss(4294967294): 9223372030412324865 (0x7FFFFFFE80000001)
  sum_acc(4294967294): 9223372030412324865 (0x7FFFFFFE80000001)
      sum(4294967294): 9223372030412324865 (0x7FFFFFFE80000001)

sum_gauss(4294967295): 9223372034707292160 (0x7FFFFFFF80000000)
  sum_acc(4294967295): 9223372034707292160 (0x7FFFFFFF80000000)
      sum(4294967295): 9223372034707292160 (0x7FFFFFFF80000000)

Done.

As seen in the image above, the simple implementation (sum) failed while the other 2 passed (for a certain (big) input value). Not sure though why it didn't also fail on Linux (WSL), most likely one of the optimizations (from -O2) enabled tail-end-recursion (or increased the stack?).

Answer 2

If this program were implemented correctly, it would work like this: When n is 1, the function returns 1. When n is 2, the function calls itself for n is 1, so it gets 1, and then adds n (i.e., 2) to it. When n is 3, the function calls itself for n is 2, so it gets 3, and then adds n (i.e., 3) to it. And so on.

Answer 3

If I understand your question correctly, you're more interested in how recursion actually works, than in the error produced by the missing return statement (see any of the other answers).

So here's my personal guide to understanding recurive functions.

If you know about Mathematical Induction, this might help understand how recursion works (a least it did for me). You prove a base case(, make an assumption about a fixed value) and prove the statement for a following number. In programming we do a very similar thing.

Firstly, identify your base cases, i.e. some input to the function that you know what the output is. In your example this is

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

Now, we need to find a way to compute the value for any given input from "smaller" inputs; in this case sum(n) = sum(n-1) +n.

How does backtracking work after the base case has been reached?

To understand this, picture the function call sum(2). We first find that 2 does not match our base case, so we recursively call the function with sum(2-1). You can imagine this recursive call as the function called with sum(2) halting until sum(1) has returned a result. Now sum(1) is the "active" function, and we find that it matches our base case, so we return 1. This is now returned to where sum(2) has waited for the result, and this function now can compute 2 + sum(1), because we got the result from the recursive call. This goes on like this for every recursive call, that is made.

Interested in a bit more low-level explanation?

In assembly (MIPS), your code would look something like this:

sum:
addi $t1, $0, 1     # store '1' in $t0
beq $a0, $t0, base  # IF n == 1: GOTO base
                    # ELSE:
                    # prepare for recursive call:
sw $a0, 4($sp)      #   write n on top of the stack
sw %ra, 8($sp)      #   write the line of the caller on top of stack
addi $sp, $sp, 8    #   advance stack pointer
addi $a0, $a0, -1   #   n = n-1
jal sum             #   call sum with reduced n
                    # this is executed AFTER the recursive call
addi $sp, $sp, -8   #   reset stack pointer
lw %ra, 8($sp)      #   load where to exit the function
lw %a0, 4($sp)      #   load the original n this instance of sum got
add %v0, %a0, %v0   #   add our n to the result of sum(n-1)
jr %ra              #   return to wherever sum() was called
base:               # this is only executed when base case is reached
add %v0, %0, %t1    #   write '1' as return statement of base case
jr %ra              #   reutrn to caller

Anytime the recursive function is called, we temporarily store the argument the current function got ($a0) and the calling function ($ra) on the stack. That's basically a LIFO storage, and we can access the top of it using the stack pointer $sp. So when we enter recursion, we want to make room on the stack for whatever we need to store there by advancing the stack pointer(addi $sp, $sp, 8); we can now store whatever we need there.

When this is done, we manipulate the argument we got (function arguments are always stored in $a0 in MIPS so we need to overwrite the argument we got). We write n-1 as argument for our recursive call and proceed to 'jump and lin' (jal) to the beginning of the function. This jumps to the provided label (start of our function) and saves the current line of code in $ra so we can return here after the function call. For every recursive call we make, the stack grows, because we store our data there, so we need to remember to reset it lateron.

Once a function call gets the argument 1, the programm jumps to base, we can simply write 1 into the designated return register ($v0), and jump back to the line of code we were called from.

This is the line where we used jal to jump back to the beginning. Since the called function provided the result of the base case in $v0,we can simply add our argument to $v0and return. However we first need to recover the argument and the return address from the stack. We also decrement the stack pointer, so that it is in the exact position where it was when the function was called. Therefore all recursive calls work together to compute the overall result; every idividual call has it's own storage on the stack, but it also ensures to tidy up before exiting, so that all the other calls can access their respective data.

The takeaway is: When calling a function recursively, execution jumps back to the beginning of the function with altered arguments. However, every individual function call handles their own set of variables (temporarily store on the stack). After a recursive call returns a value, the next most-inner recursive call becomes active, re-loads all their variables and computes the next result.

Answer 4

How this code backtracks itself afterwards..?

It doesn't certainly work.

Any success is due to undefined behavior (UB).

The biggest mistake is not compiling with a well enabled compiler.

int sum(int n)
{
    if(n==1)
    {
        return 1;
    }
   int sumNm1=sum(n-1); //sum of 1 to n 
   int sumN=sumNm1+n;                   // !! What, no warning?
}                                       // !! What, no warning?

A well enabled compiler generates warnings something like the below.

warning: unused variable 'sumN' [-Wunused-variable]
warning: control reaches end of non-void function [-Wreturn-type]

Save time and enable all compiler warnings. You get faster feedback to code troubles than posting on SO.

   int sumN=sumNm1+n;
   return sumN;  // Add
}

  

Answer 5

The code needs a return statement in the case where n is not 1:

int sum(int n)
{
    if(n==1)
    {
        return 1;
    }
    int sumNm1=sum(n-1); //sum of 1 to n
    int sumN=sumNm1+n;
    return sumN;
}

or more simply:

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

How this code backtracks itself afterwards..?

When a function is called, the program saves information about hwo to get back to the calling context. When return statement is executed, the program uses the saved information to return to the calling context.

This is usually implemented via a hardware stack, a region of memory set aside for this purpose. There is a stack pointer that points to the active portion of the stack memory. When main calls sum(5), a return address into main is pushed onto the stack, and the stack pointer is adjusted to point to memory that is then used for the local variables in sum. When sum calls sum(n-1), which is sum(4), a return address into sum is pushed onto the stack, and the stack pointer is adjusted again. This continues for sum(3), sum(2), and sum(1). For sum(1), the function returns 1, and the saved return address is used to go back to the previous execution of sum, for sum(2), and the stack pointer is adjusted in the reverse direction. Then the returned value 1 is added to its n, and 3 is returned. The saved address is used to go back to the previous execution, and the stack pointer is again adjusted in the reverse direction. This continues until the original sum(5) is executing again. It returns 15 and uses the saved address to go back to main.