1

I'm puzzled by the behavior of a recursive C function I encountered. Here's the code snippet:

#include <stdio.h> int sum_up_to_n(int n, int curr_sum) { if (n == 0) { return curr_sum; } sum_up_to_n(n - 1, n + curr_sum); } int main() { printf("%d", sum_up_to_n(3, 0)); return 0; }

Despite the absence of a return statement when if case fails in the sum_up_to_n function, it seems to be producing the correct output without any errors. Can someone explain why this behavior occurs? Shouldn't the missing return statement result in an error? or at least the compiler should warn. I'd appreciate insights into how this code functions.

Improve this question
13
  • 6
    Falling out of sum_up_to_n without a return (which happens when n != 0) causes undefined behavior. My compiler (MSVC) gives a warning: warning C4715: 'sum_up_to_n': not all control paths return a value Commented Apr 10, 2024 at 15:23
  • 2
    That is just a random result. It should be reported by the compiler. If you don't get a warning or error, you need to increase diagnostics level. For GCC or clang use -Wall -Wextra -pedantic Commented Apr 10, 2024 at 15:25
  • 5
    This code is broken. Whether it "works" on a given platform with a given compiler is a coin toss. Without a return statement in the fall-through case, the caller of sum_up_to_n could pick up anything. Bad code. Commented Apr 10, 2024 at 15:26
  • 1
    Should just be return n*(n+1)/2; without any recursion. Commented Apr 10, 2024 at 15:32
  • 2
    @wohlstad, I can imagine intentional uses, but yes, I would consider it poor style. Commented Apr 10, 2024 at 17:20

3 Answers 3

Reset to default
4

The following may "work"1 but only because one of the options available for undefined behavior is a function appearing to work. It will not "work" randomly at some point and you will be frustrated.

int sum_up_to_n(int n, int curr_sum) { if (n == 0) { return curr_sum; } sum_up_to_n(n - 1, n + curr_sum); }

But there is hope! If I compile this with warnings enabled, we can see that the compiler spots this bug.

$ cat test.c int sum_up_to_n(int n, int curr_sum) { if (n == 0) { return curr_sum; } sum_up_to_n(n - 1, n + curr_sum); } $ gcc -c -Wall -Wextra -Wpedantic test.c test.c: In function ‘sum_up_to_n’: test.c:6:1: warning: control reaches end of non-void function [-Wreturn-type] } ^

Warnings can be ignored (but shouldn't be). If I tell the compiler to treat warnings as errors, they can no longer be ignored.

$ gcc -c -Wall -Wextra -Wpedantic test.c -Werror test.c: In function ‘sum_up_to_n’: test.c:6:1: error: control reaches end of non-void function [-Werror=return-type] } ^ cc1: all warnings being treated as errors

Compiling with warnings enabled will help you catch many other potential problems in your code. Remember if you get a long series of warnings or errors to address the first one first and then recompile. Subsequent issues may have cascaded off that first problem, and "fixing" subsequent issues may not be necessary or even may be detrimental.

1 Where by "work" we mean "not detectably fail."

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

The code's behaviour is undefined. You can't rely on it producing the result you obtained. The behaviour could even change from one run to another.

Make sure to enable and heed your compiler's warnings. They would have caught this. With gcc, I use -Wall -Wextra -pedantic.

Improve this answer

Comments

1

As already been said (and as you already know), your code isn't right and it will cause an undefined behaviour (which means it'll produce different results, or may be an exception, depending on the implementation and/or the platform).

You want to know WHY it works in your case. Without knowing the specifics, we can only guess. But I'm pretty sure it's because the way parameters and return values are internally handled.

When using the "C calling convention" (edited, see the comments below), actual parameters are placed by the calling function into the stack. The called function reads these parameters but doesn't adjust the stack pointer. After the called function has returned, the calling function adjusts the stack pointer ("removing" the parameters from the stack). (Other calling conventions do things in a different way. In Pascal, for instance, is usually the calle responsibility to clear the stack.) Doesn't matter if the caller and the calle are the same function (that is, if the share the same code).

But the return value is handled differently; and, if I remember well, that's not defined by the specification. Usually, the return value is just "passed up" to the calling function using a CPU register (R0, AX, etc) (this is usually dependant on the calling convention of the platform, if it has one).

In your case, the only return value that matters is the last one. (Actually, that's your only return value, the one when (n == 0), because your code is not recursive in the usual way. It doesn't depend on the return value of each "internal" call. it just uses recursion for adding up the curr_sum. About that, check @stark comment.)

Then, when the recursive function hits (n == 0), it puts the cumulated curr_sum into its target destination (let's say it's register R0) and begins the unwinding. Each subsequent return will just do that: return to the calling function, without overwriting the "result" stored in R0. Finally, the main function will read this result, assuming it's from the function it directly called, the first iteration of sum_up_to_n().

Also, the compiler may be avoiding the (in your case) unneeded recursion and may be doing some kind of optimization, converting it into a simple loop.

Improve this answer

5 Comments

Re “In C (as per language specification), actual parameters are placed by the calling function into the stack”: The C standard says nothing about how arguments are passed. Current common C implementations pass the first few arguments in registers, unless they are large.
You're right about the specification. Strictly speaking, putting actual parameters in an agreed place is enough. But some kind of stack-like structure is necessary for allowing recursive calls (recursive calls are mandatory for the C language, and recursion is a key point in this specific question). And that's not just for saving the return address, but also for preserving the locality of the parameters. Actually, it's the same with all local variables (formal parameters ARE local variables inside the function).
If you pass parameters using registers (or using a predefined memory area, etc), you MUST preserve the content of such registers (or such memory area) before the next call. This is specially important because recursion may be indirect (and not always obvious for the compiler). I would say passing parameters using registers is just a (very common) optimization technique, where you are avoiding the PUSH (by the caller), the MOVE/LOAD (it's not a POP) by the calle, and a later stack pointer adjustment (by the caller, at least when using what is usually called "the C calling convention").
The development of a stack-like structure is key to the development of computers and programming languages, for easily allowing recursion and some types of reentrancy. The C language (as Unix) was developed on a PDP-11, which had a "hardware stack" (actually, indirect addressing with auto-decrement/auto-increment using the R6/SP register). It's direct predecessor, the much simpler PDP-8, didn't have a stack, saved the return address at the beginning of the called routine (recursion and reentrancy were possible, with additional work), and didn't have a predefined method for parameter passing.
The VAX (the direct successor of the PDP-11, and the first machine where a really protected mode Unix ran) also included a couple of instructions for calling routines and passing parameters using the a stack-like structure. CALLS used the "hardware stack", and CALLG used a separate memory area. For the called routine, it was exactly the same, with the R12/AP register pointing to the actual parameters (and the stack adjustment automatically done by the RETurn instruction, just for CALLS). Other "PDP-11 inspired" designs (including almost all Intel microprocessors) also had a "hardware stack".

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.