Discussion on: Write a function that shows off something unique or interesting about the language you're using

And another one. C++ can do some pretty impressive things at build time. In the case of Fibonacci, we can declare it as a template function, and let it get calculated during compilation:

#include <iostream>

template<int i> int fib() {
        return fib<i-1>() + fib<i-2>();
}
template<> int fib<0>() {
        return 0;
}
template<> int fib<1>() {
        return 1;
}

int main(int argc, const char ** argv) {
        std::cout << fib<20>() << std::endl;
}

In the above, there's no recursion at runtime - it's all in the compiler.

Or, in C++ 11 and beyond, we get constexpr, which will give us the same thing, but allow the function to be called normally at runtime as well:

#include <iostream>

constexpr int fib(int i) {
        if (i == 0) return 0;
        if (i == 1) return 1;
        return fib(i-1) + fib(i-2);
}

int main(int argc, const char ** argv) {
        std::cout << fib(20) << std::endl;
}

This (I think) is still calculating the result at compile time - but if we used a variable instead of 20, it'd calculate it at compile time. As far as whether the code would recurse twice at each level, though, that's up to how clever the compiler is feeling - we've told it (with constexpr that the results are always the same).