Consider this recursive function:

bool foo(u_int d){
    if (d > 1) return foo(d - 1) or foo(d - 2);
    return true;
}

This function returns true for all values of d. If it were evaluated naively, it would make O(F_n) recursive calls, where F_n is the nth Fibonacci number.

However, "or" expressions are evaluated efficiently. If one term is true, the other is not evaluated since it won't change the value of the expression. Therefore foo(d-2) is never called, so the complexity of the function is O(d).

I checked this by calling foo(100), which finished very quickly. F_100≈3.5e20, so there is no way so many recursive calls were made.

If we swap the "or" for an "and" and the "true" for a "false" it behaves very similarly, since "and" expressions are also optimized.

bool foo(u_int d){
    if (d > 1) return foo(d - 1) and foo(d - 2);
    return false;
}

Now consider this function:

int bar(){
    return 0 * bar();
}

This causes an infinite recursion, even though 0 * something is always 0.

I also tried the following function:

int bar(u_int d){
    if (d > 1) return 0 * bar(d - 1) * bar(d - 2);
    return 1;
}

Here all of the recursive calls are made too. I ran bar(40) and there was a noticeable delay. I compared the runtime of the function bar to baz

bool baz(u_int d){
    if (d > 2) return baz(d - 1) and baz(d - 2);
    return true;
}

and they are quite similar. They both make O(F_n) recursive calls.

My question is why isn't multiplication optimized in a similar way as the boolean expressions. 0 * something is always 0, so there is no need to evaluate the recursive calls.

Consider this recursive function:

bool foo(u_int d){
    if (d > 1) return foo(d - 1) or foo(d - 2);
    return true;
}

This function returns true for all values of d. If it were evaluated naively, it would make O(F_n) recursive calls, where F_n is the nth Fibonacci number.

However, "or" expressions are evaluated efficiently. If one term is true, the other is not evaluated since it won't change the value of the expression. Therefore foo(d-2) is never called, so the complexity of the function is O(d).

I checked this by calling foo(100), which finished very quickly. F_100≈3.5e20, so there is no way so many recursive calls were made.

If we swap the "or" for an "and" and the "true" for a "false" it behaves very similarly, since "and" expressions are also optimized.

bool foo(u_int d){
    if (d > 1) return foo(d - 1) and foo(d - 2);
    return false;
}

Now consider this function:

int bar(){
    return 0 * bar();
}

This causes an infinite recursion, even though 0 * something is always 0.

I also tried the following function:

int bar(u_int d){
    if (d > 1) return 0 * bar(d - 1) * bar(d - 2);
    return 1;
}

Here all of the recursive calls are made too. I ran bar(40) and there was a noticeable delay. I compared the runtime of the function bar to baz

bool baz(u_int d){
    if (d > 2) return baz(d - 1) and baz(d - 2);
    return true;
}

and they are quite similar. They both make O(F_n) recursive calls.

My question is why isn't multiplication optimized in a similar way as the boolean expressions. 0 * something is always 0, so there is no need to evaluate the recursive calls.

• c++
• recursion

• 1 you can count how often the function is called no need to speculate – 463035818_is_not_an_ai Commented Feb 7 at 11:52
• 1 "0 * something is always 0" is a false premise. FOr example 0 * 1/0 is not defined. – 463035818_is_not_an_ai Commented Feb 7 at 11:52
• 1 return 0 * bar(); is UB with infinite recursive call, your other example don't have infinite loops. – Jarod42 Commented Feb 7 at 11:56
• 1 eel.is/c++draft/intro.progress <- the 0 recursion seems to break the forward progress assumption and is not a trivial infinite loop, so it is undefined behavior and the compiler is free to do anything it feels like there, including silly stuff – teapot418 Commented Feb 7 at 12:01
• 3 "But "bar" always returns an integer, and 0 * an integer is always 0." how do you know that bar always returns an integer? THink about it for some more time... you need infinite recursions to be really sure... and eventually you see that it never returns – 463035818_is_not_an_ai Commented Feb 7 at 12:11

3 Answers 3

This difference between arithmetic and logical operators is due to how the operators were used historically (and are intended to be used), not due to their mathematical properties.

Suppose we have a linked list and a pointer p that points to the first item in the list if there is one (and is null otherwise), and we want to work with the second item in the list, p->next, if it exists. Some early C code would use a construction like this:

if (p && p->next)
{
    // Operate on *p->next.
}

This code relies on p->next being evaluated only if p is non-null, as otherwise p->next would dereference a null pointer. The C language was designed to support that; it was made a rule that the right operand of && is evaluated only if the left operand evaluates as true. This was a valued feature of C, as brevity was favored by the economics of computing at the time, and, overall, practitioners found it intuitive and aesthetic. C++ inherited this design.

Mathematically, we could specify a programming language in which E0 * E1 evaluated expression E1 if and only if E0 were non-zero (at least for integer operands; floating-point has complications) or a programming language in which E0 && E1 always evaluated both operands. However, the former then requires that E0 always be evaluated and tested before E1 is evaluated. That introduces extra work (in the test) and impedes optimization (because it introduces a sequencing constraint).

Of course, the latter, specifying that E0 && E1 evaluate E1 if and only if E0 is true also requires a test and introduces a sequencing constraint. However, we write code with this in mind: When we write code with &&, we write it with this rule in mind. Thus, the rule for how && behaves arises out of our choices of how to use the programming language, not out of any mathematical requirement.

Similarly, * is an operator we use repeatedly in mathematical expressions. One expression may have many * operators, and we do not want to introduce many tests for zero and many sequencing constraints. Mathematically, the result might be the same, but the computational cost would be increased.

Consider this code, and yes, printf returns an int.

0 * printf("Hello, world!\n");

Performing the optimization you're talking about would change the behavior of the above code.

The fact that E0 && E1 only evaluates E1 if E0 has been evaluated to true is not really an optimization. It's a part of the language. E1 is not even allowed to evaluate unless E0 is true.

Built-in or (and and) must do short cuirciting, this is how they are defined by the language. There is no short cuirciting for *.

To see whether return 0 * bar(); eventually returns or throws an exception is generally an unsolvable problem at compile time. Moreover, if bar() has side effect then optimizations cannot remove the call. In your case the effect is that you have an infinite recursion, which is actually undefined behavior.