Recursive function with stopping condition but without base case still works

Question

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)?

Undefined Behaviour is just that - *undefined*. In your case, not initializing `sum` means that it's starting value could be anything ... including zero. — Adrian Mole, Apr 23 '21 at 20:54
The value of `sumUpTo(0)` is "known" in that the loop does not run. That means `sum=0` needs to be initialized. Failing to initialize it results in nonsense (undefined behaviour) output. — tadman, Apr 23 '21 at 20:54
*even with/without initialization of the variable sum*. That's Undefined Behaviour. With UB the result is unpredictable. It can get a garbage value, it can crash it can even appear to "work". But code with UB can fail at any time. [Undefined, unspecified and implementation-defined behavior](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior) — kaylum, Apr 23 '21 at 20:54
Does this answer your question? [What happens to a declared, uninitialized variable in C? Does it have a value?](https://stackoverflow.com/questions/1597405/what-happens-to-a-declared-uninitialized-variable-in-c-does-it-have-a-value) — kaylum, Apr 23 '21 at 20:55
Tip: Usually you use loops *or* recursion, not both. If you end up with both in your solution, check your algorithm carefully because you might be mixing up two valid approaches to the problem that do not work when combined. — tadman, Apr 23 '21 at 21:02
Your loop repeatedly (for `num>1`) assigns to `sum`, throwing away every value but the last. — Davis Herring, Apr 23 '21 at 21:27
Your `for`-loop is unnecessary. As @DavisHerring says it either does not run or only stores the value of the last iteration. Hence the `for`-statement has an effect equivalent to `if(num>0) ...`. Therefore, you did implement the base case (`num <= 0`) where the recursion is not invoked. — nielsen, Apr 23 '21 at 21:49
After reading the answer I believe it's Undefined Behaviour in the case I don't initialize sum. When I initialize it the loop doesn't start and so I set the base case of sumUpTo(0) = 0 without realizing it. Thanks! — Noah, Apr 23 '21 at 23:37
Your image of text [isn't very helpful](//unix.meta.stackexchange.com/q/4086). It can't be read aloud or copied into an editor, and it doesn't index very well, meaning that other users with the same problem are less likely to find the answer here. Please [edit] your post to incorporate the relevant text directly (preferably using copy+paste to avoid transcription errors). — Toby Speight, Apr 24 '21 at 07:28

Devolus · Answer 1 · 2021-04-23T21:23:46.650

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.

top talent · Accepted Answer · 2021-04-23T21:20:49.460

1

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;
}

edited Apr 23 '21 at 21:20

answered Apr 23 '21 at 21:01

top talent

615
4
17

1

In the standard code there's no loop, just a recursive call. – tadman Apr 23 '21 at 21:02

score 0 · Answer 3 · answered Apr 23 '21 at 20:54

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..

Recursive function with stopping condition but without base case still works

3 Answers3