Why does a recursed return call break out of stack

问题:

I was shown a sample program to demonstrate recursion which looks like it should not work but does. The logic is pretty clear but why does it work even when the recursed function call is not returned? It seems like the return command breaks out of the stack even if it isn't requested to. Is this a language standard or a gcc thing? I saw it with C and C++ compiled with gcc on Windows and Linux.

#include <iostream>
#include <cstdlib>

using namespace std;

int isprime(int num, int i)
{
   if (i == 1) {
      return 1;
   }
   else {
      if (num % i == 0)
         return 0;
      else
         isprime(num, i-1); // should be returned
   }
}


int main(int argc, char** argv)
{
   int input = atoi(argv[1]);
   cout << input << "\t" << isprime(input, input/2) << "\n";
}

回答1:

Things like that only work if accidentally the return value happens to be in the register where the caller expects it. This only works if this is realized by your compiler as a recursive function. Technically it is undefined behavior to use the return value of a function that doesn't provide one.

Edit: On modern architectures the return value of a function for values for which it is possible is passed in a specific hardware register. When you call your function recursively, on the bottom in all cases that hardware register is set to the expect value. If by chance when popping up from recursion that hardware register is never changed, you end up with the correct value.

All of this pattern wouldn't work, if the return value would be placed at some location of the stacks of the (recursive) callers.

In any case, all of that should be captured by any modern compiler and give you a warning. If it doesn't you don't have a good compiler, or you are using too defensive command line options.

New year's eve special: In the real world, code like this (with the return) wouldn't even be realized as a recursive function. With not too much effort you will find an iterative variant of that function, and any modern decent compiler should be able to find it as well if you ask for maximal optimization.

回答2:

A lot here depends what you mean by "it works"?

to try and answer the main point of your question, functions will return when the end of the function is reached, whether or not a return statement is met.

I would expect to see compiler warnings telling you the possible controls paths may not return a value, in C++ at any rate. Resulting in undefined behaviour, see this question: not returning a value from a non-void returning function

I would say that this example "works" as after a prime is found and isPrime has returned, then the next function up the stack is also free to return. Nothing depends on the return value of isPrime either, so the program will run back up the stack and output something.

...but as behaviour is undefined, the value that actually gets output is likely to be junk. If you are seeing 0 & 1 consistent with primes as input, then wow.

If you think this is working, I would look at testing more broadly with different values.

Also have you been building with any "debug" settings? if so try this again with debug settings off, as thiese sometimes do extra work to keep things uninitialised memory clean.

回答3:

I can explain exactly what happens:

The function is called, and it recurses back into itself until it reaches the return at either modulo (return 0) or end of recursion (return 1). At this point the function reuturns to the caller, which is is_prime. But there is no more code in the function to execute, so it immediately returns without any further action.

However, you could easily break this by, for example, add printf("Done for %d, %d\n", num, i); behind the call of is_prime() [doesn't have to be in the if-statement]. Or adding a C++ object that is created and destroyed on entry/exit of the function, as another example.

You're just being lucky that it works. And it's very fragile and easy to break - compile it with a different compiler (or with different optimization settings, or a new version of the compiler, or a million other things), and it may well break.

回答4:

Aren't you forgetting a return statement? For normal recursion you need to put a return before isprime(num,i-1); as well.

I guess this even should give a compile warning if you compile this using strict rules, because the function must always return an int, now it does not (at least if your compiler does not fix this).