Recursive function with stopping condition but without base case still works

user_15599747 0
Viewed 195

I tried to solve the problem by calculating sum up to n without knowing about the base case and come up with this. It works but I don't know why.

int sumUpTo(int num)
{
    int i, sum = 0;      // I also tried not to initialize sum here but the results are the same
    for(i = 0; i < num; i++)
        sum = sumUpTo(num - 1) + num;
    return sum;
}

int main()
{
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    printf("Sum = %d\n", sumUpTo(num));
    return 0;
}

I figured out that this function has the stopping condition i=num but no base case, the loop will stop with sum = sumUpTo(0) + 1 + ... + num. How could the program work without knowing the value of sumUpTo(0)? What could possibly happen here? Did the program assume the value of sumUpTo(0) is 0 (even with/without initialization of the variable sum)?

c
3 Answers

Suppose you enter 3 as your input.

for(i = 0; i < 3; i++)   // Returns 3 + 3 = 6
    for(i = 0; i < 2; i++)   // Returns 2 + 1 = 3
        for(i = 0; i < 1; i++)   // Returns 1 + 0 = 1
            for(i = 0; i < 0; i++) // Returns 0

Here the recursion will end because that will not call another instance

If you don't initialize sum, as your comment says, the function can still work, only the result is undetermined.

user_22820110
  • You didn't set base value of num variable, but it works successfully This is specific case of your code.
  • In this code, you used 'for' statement If incoming num is 0, it doesn't pass via 'for' statement because 0 < 0 is not true. that's why it returns initial sum value with zero in last final loop
  • Take this reference for safe algorithm, This is the standard code for recursive function
int sumUpTo(int num)
{
    if(num == 0)
      return 0;
    return sumUpTo(num - 1) + num;
}
user_148129510

It works as in your for loop you have

for(i = 0; i < num; i++)

if num is a 0 or lower the for loop would never execute and since you have

int sum = 0;

it will return 0 as it never entered the for loop and everytime your function gets restarted(recalled) it will the current copy of num to 0..

user_99274900
Related