Unnecessary recursion calls

Question

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.

Answer 1

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.