0

When David was taking about these two codes:

int sigma(int m)
{

  if (m <= 0)
    return 0;

  else
    return (m + sigma(m - 1));
}

and

int sigma(int m)
{
  return (m + sigma(m - 1));
}

I understand that if a function calls itself infinite number of times, the program will crash because of exceeding allocated stack memory. However, I do not understand why when you input 50 for both codes. The second one will crash but not the first one. It seems 50 fulfills m>0 condition.

1
int sigma(int m)

{
    if (m <= 0)
        return 0;
    else
        return (m + sigma(m - 1)); 
}

The last line is where "magic" happens, because sigma calls itself with m decremented by one each time, each call is getting closer and closer to our base case of m = 0.

When m = 0, our function will reverse, instead of adding to the stack, it will remove layers of the stack in reverse order until we get our answers. Here's a quick idea of what it will do:

if you call:
    sigma(4);


sigma(4) // answer depends on whatever sigma(3) is
sigma(3) // answer depends on whatever sigma(2) is
sigma(2) // answer depends on whatever sigma(1) is
sigma(1) // answer depends on whatever sigma(0) is

sigma(0) // we know that sigma(0) is 0. So we return 0 to sigma(1)   

sigma(1) = (1 + 0) // so sigma(1) is 1. So we return 1 to sigma(2)
sigma(2) = (2 + 1) // so sigma(2) is 3. So we return 3 to sigma(3)
sigma(3) = (3 + 3) // so sigma(3) is 6. So we return 6 to sigma(4)
sigma(4) = (4 + 6) // so sigma(4) is 10. So we return 10 to whoever asked us.

Hope that helps!

3
  • Thanks, that was really helpful. One more question though, doesn't the function sigma() itself has a condition of m < 0? in the earlier of the talk? int sigma(int m) { // avoid risk of infinite loop if (m < 1) { return 0; } // return sum of 1 through m int sum = 0; for (int i = 1; i <= m; i++) { sum += i; } return sum; } – Yinzhou Zhu Feb 23 '15 at 23:51
  • Oh, nvm, I totally mixed up the 3 codes provided in the lecture. I thought, the code uses a previously defined function sigma(). But it actually is the sigma itself. That's why this is a recursion function. And in this case(the correct recursion function) the return 0 is returning an actual number 0 right? – Yinzhou Zhu Feb 23 '15 at 23:57
  • Yep, that's right the last function call will return 0 – Antoine Wood Feb 24 '15 at 5:12
1

A recursive function typically consists of two main steps

  1. base case step
  2. recursive step

A recursive function basically keeps calling itself until the base case is reached. In the first example above, the base case is m <= 0. It appears from the recursive call (i.e., sigma(m - 1)) that the argument of the function sigma is decreased by 1 which means that it will eventually become 0 at some point in which case there will be no more recursive calls (i.e., the statement return 0 is executed).

In the second example, there is NO base case which means that there is no specified point at which the function will stop calling itself. And since the stack is finite, you'll eventually get an error.

1
  • Got it! I got confused with the non-recursive and recursive versions of the codes provided in the lecture. I thought the sigma() function is defined somewhere else. But after looking at it more carefully, I realized that the two codes I showed above are the sigma itself. Now I understand the recursion that was talked about. Thanks! – Yinzhou Zhu Feb 24 '15 at 0:04

You must log in to answer this question.

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