0

I am having trouble understanding how the recursion in following code works. So I do understand that main prints the user input. Then the function sigma will print + and a decrementation of m until it reaches 0.

When it reaches 0 it will print = and the variable answer. What I do not understand is how return calculates the numbers together. Could anybody please explain how the return is doing this?

#include <cs50.h>
#include <stdio.h>

int sigma(int m)
{
    printf("%i", m);
    if (m == 0)
    {
        printf("=");
        return 0;
    }
    else
    {
        printf("+");
        return (m + sigma(m - 1));
    }
}

int main(void)
{
    int n = GetInt();
    int answer = sigma(n);
    printf("%i\n", answer);
}
2

Unroll sigma (5) and see what you get ..

sigma (5) = 5 + sigma (4)
      = 5 + (4 + sigma (3))
      = 5 + (4 + (3 + sigma (2)))
      = 5 + (4 + (3 + (2 + sigma (1))))
      = 5 + (4 + (3 + (2 + (1 + sigma (0)))))
      = 5 + (4 + (3 + (2 + (1 + 0))))
      = 5 + (4 + (3 + (2 + 1)))
      = 5 + (4 + (3 + 3))
      = 5 + (4 + 6)
      = 5 + 10
      = 15

Note that calling sigma with a negative parameter will break your program.

| improve this answer | |
  • With your base case (m = 0) and your stepwise descent from any positive m down to the base case, this recursion is basically mathematical induction, but backwards. – Nick Sifniotis Jul 12 '15 at 15:34
  • So every time return (m + sigma(m - 1) happens the int m is stored there? I find it confusing how in the end it just calculates all the number together. – Verpoorten Nick Jul 12 '15 at 16:26
  • I don't understand - is my example not clear enough? What I wrote is exactly how the function calls are evaluated, step by step. – Nick Sifniotis Jul 13 '15 at 12:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .