Why does this kind of recursion work in C++?

Question

I made a recursive C++ program that looks like this:

using namespace std;
#include <iostream>

bool recursive(int num)
{
    if (num == 6)
    {
        return false;
    }

    else if (num > 6)
    {
        return true;
    }

    else
    {
        if (recursive(num + 1))
        {
            return true;
        }

        else
        {
            return false;
        }
    }
}


int main()
{
    if (recursive(0))
    {
        cout << "Not found!" << endl;
    }

    else
    {
        cout << "Found..." << endl;
    }
}

It works and I assumed that this was (roughly) the best way to do it.

My friend made a simpler recursive program that looks like this:

using namespace std;
#include <iostream>

bool recursive(int num)
{
    if (num == 6)
    {
        return false;
    }

    else if (num > 6)
    {
        return true;
    }

    else
    {
        recursive(num + 1);
    }
}


int main()
{
    if (recursive(0))
    {
        cout << "Not found!" << endl;
    }

    else
    {
        cout << "Found..." << endl;
    }
}

His works just like mine does, but I don't understand why it works. To me, it looks like nothing gets returned in his else block, so I don't understand how the boolean value gets returned to the original function call.

Out of curiosity, I made a similar program in JavaScript:

function recursive(index)
{
    if (index == 6)
    {
        return true;
    }

    else if (index > 6)
    {
        return false;
    }

    else
    {
        recursive(index + 1);
    }
}

if (recursive(0))
{
    console.log("found");
}

else
{
    console.log("not found");
}

But the JavaScript program doesn't work, which makes me think that this is specific to C++.

Why does my friend's program work? Is it completely valid, or is it undefined behavior?

Your original code has 25 lines. This seems ridiculously excessive; so excessive, in fact, that Stack Overflow doesn’t display your full code, the reader is forced to scroll down in the code box. You can fit the same function *comfortably* into seven lines. You can even reduce the logic to one line while still staying readable: `return num < 6 ? recursive(num + 1) : num > 6;`. But in a real application you should forego recursion: `return num > 6;`. — Konrad Rudolph, Nov 10 '16 at 22:14

John Kugelman · Accepted Answer · 2016-11-10T22:09:48.600

Why does it work? Answer: it doesn't.

else
{
    recursive(num + 1);
}

Your friend's program is missing a return statement.

else
{
    return recursive(num + 1);
}

Not returning a value from a non-void function leads to undefined behavior.

In this case, it so happens that on the computer you tested on the return value from the recursive call was automatically "returned" to the caller -- perhaps because it happened to be in the right register. This is pure happenstance. You can't rely on it. On a different machine, or different compiler, or even a different invocation, the program could just as well return something else, or crash, or do anything else you can imagine.

score 3 · Answer 2 · answered Nov 10 '16 at 22:12

Ending a function without a return statement is undefined behavior in C++. The best I can do is speculate as to what's happening, and my best guess is that the call to recursive(index + 1), being the last thing on the stack before the function returns, is getting picked up as the return value. So in a (non-standard, non-portable, very poorly advised for general use) sense, the code has implicitly inserted the return statement.

score 2 · Answer 3 · answered Nov 10 '16 at 22:03

2

This is undefined behavior. Since the function is declared to return boolean, it will always return something, but not necessarily the right value.

If you compile with -Wall flag, compilers like GCC will give you a warning for this kind of code.

answered Nov 10 '16 at 22:03

SPMP

1,181
1
9
24

score 2 · Answer 4 · edited Jun 20 '20 at 09:12

Sure, it works! Well, not really.

Every compiler on Earth (maybe not) will warn you:

clang: control may reach end of non-void function

gcc: control reaches end of non-void function

MVSC: not all control paths return a value

It does work because your friend was lucky enough not to have this program explode, implode or create a black hole in your bedroom. Undefined Behavior is what it is: You can't tell how your program will behave.

This is what the standard has to say about it:

Flowing off the end of a constructor, a destructor, or a function with a cv void return type is equivalent to a return with no operand. Otherwise, flowing off the end of a function other than main (3.6.1) results in undefined behavior.

Why does this kind of recursion work in C++?

4 Answers4