Bailing early from a recursive function

Question

I'm playing around with recursive functions a bit, and here is what I have for seeing if an array contains a value:

bool val_in_array_r(int val, int array[], size_t size)
{
    if (!size)
        return false;
    else
        return (val == *array)|| val_in_array_r(val, array+1, size-1);
}

One question I have here, is I could have an array of a billion entries, and the 10,000th one returns true. Instead of having to continue and getting:

false || false || ... || true || false || false || ...

Is there a way to exit early if the case is met? Or this is just not something a recursive function can do?

It seems to me (theoretically) doing something like that would need to be super low-level, as it'd need to keep track of the initial call frame of the first time val_in_array_r is called, and then jump back to that rbp, then replace rsp and do ret.

Short answer is no. Each recursive call *winds-in* another level of recursion. When you `return`, you are returning to the calling function which was the previous recursive call. (returning from a recursive function unwinds). I would not suggest a `goto` to jump out of multiple recursive calls, but conceivably, so long as it qualified as a "near-jump" it should be possible. — David C. Rankin, Mar 23 '21 at 04:56
@carl.hiass Tail recursion, where detectable, is optimized by most modern compilers. Likely it wouldn't even recurse at all. — David Schwartz, Mar 23 '21 at 04:57
@DavidSchwartz I updated the question to say it's not the first one, sorry for the error in that initially. Re: optimizing/tail-recursion, yes let's say it's not optimized by the compiler -- I'm just curious from a theoretical/academic standpoint. — carl.hiass, Mar 23 '21 at 04:57
@DavidC.Rankin what is a "near jump"? Want to show an example of how it could be done? — carl.hiass, Mar 23 '21 at 04:59
A "near-jump" is an older term that limited the destination address to being within the same memory segment. Today, a jump within the same segment isn't the technical limit (it is much less that an entire segment now with 32/64-bit allowing access to gigabytes worth of memory), but the near-jump term implies a jump to a nearby address. See comments and links in [How does the GNU toolchain decide to use near vs. short jump instructions?](https://stackoverflow.com/q/60715920/3422102) — David C. Rankin, Mar 23 '21 at 05:06

score 3 · Accepted Answer · answered Mar 23 '21 at 04:59

I would suggest transforming the code slightly to make things absolutely clear:

if (!size)
    return false;
else if (val == *array)
    return true;
return val_in_array_r(val, array+1, size-1);

Now, it's absolutely clear that this is tail recursion. A modern compiler should have no difficulty optimizing it, most likely removing the recursion entirely and just looping back to the beginning of the function.

The compiler should have no trouble optimizing that to:

while (1)
{
    if (!size)
        return false;
    else if (val == *array)
        return true;
    ++array;
    --size;
}

I suspect a good, modern compiler would recognize the tail recursion even in the original code and make the same optimization. But it never hurts to be sure. Personally, I almost always prefer to convert recursive algorithms to iterative ones to ensure predictability, avoid overflowing stacks, and simplify maintaining the code.

The preference and advice would be worth 2 votes if I could give them. — David C. Rankin, Mar 23 '21 at 05:11

Bailing early from a recursive function

1 Answers1