What does bind time have to do with recursion in C plus plus?

Answer 1

In C++, names are either statically bound at compile time, dynamically bound at runtime or (with compile time computation) not bound at all.

With respect to functions, dynamic binding only occurs when a function is invoked through a function pointer. This also applies to virtual functions because the virtual function table (vtable) is simply a list of function pointers that apply specifically to the runtime class of the object the function is invoked against. If we do not know the runtime type (the actual type) of an object at compile time, then we cannot statically bind a virtual function call at compile time. Instead, the compiler must generate code to perform a vtable lookup and then invoke the appropriate function dynamically. However, if the runtime type is known at compile time, then we can statically bind to a virtual function.

Static binding is faster than dynamic binding because we eliminate the indirection required to invoke a function via a pointer variable. Although we can write code to determine the runtime type of an object and thus statically bind all function calls, the overhead far outweighs the otherwise trivial cost of an indirection.

In the case of recursive functions, dynamic binding can only occur if we invoke the function through a function pointer. Once invoked, all recursive calls to that same function are statically bound:

unsigned object::fact (unsigned x) {

return x<2 ? 1 : x * (fact (x-1));

}

Here, the name fact used within the function is implicitly bound to this->fact and is therefore statically bound to object::fact. The initial invocation may or may not have been dynamically bound, but that has no bearing once the function is invoked.

If a function is declared constant expression (constexpr) and is used in a constant expression, the function call (and its binding) can be eliminated completely. Consider the following:

constexpr unsigned fact (const unsigned num) {

return num < 2 ? 1 : num * fact (num - 1);

}

void f () {

unsigned x = fact (7);

// ...

}

A good compiler will replace all of the above with the following:

void f () { unsigned x = 5040;

// ...

}

This is known as compile-time computation. We get the convenience of a function (even a recursive one) but with none of the runtime cost. And since the function is not required at runtime, there is nothing to bind to. However, constant expression functions are useful in that they can also be used in expressions that are not constant. For example:

void g (unsigned x) {

unsigned y = fact (x);

// ...

}

The above call to fact cannot be computed at compile time because x is not constant, so the compiler must statically bind the function instead. Thus we get the advantage of compile time computation when it is possible to do so and static binding when it is not.

If we wish to prevent static binding completely, then we need to use template metaprogramming instead:

template<unsigned N>

constexpr unsigned fact() {

return N * fact<N-1>();

}

template<>

constexpr unsigned fact<1>() {

return 1;

}

template<>

constexpr unsigned fact<0>() {

return 1;

}

Note that we must use specialisation to handle the end cases (where N is 0 or 1). It is not as elegant as the plain constexpr version, however it does guarantee that we only use compile time computation rather than static binding:

void h (unsigned x) {

unsigned y = fact<7>(); // OK: generates equivalent code to unsigned x = 5040;

unsigned z = fact<x>(); // error: x is not constexpr

// ...

}