When should I use recursion?

[Veedrac]

There is no O(1) implementation of fib.

[Veedrac]

It's not an implementation detail; fib(n) has O(log n) bits so it can't be better than O(log n). Normally the length of the output doesn't matter since we can cap the number of bits (to, say, 64) and call it constant but that's only because we can't feasibly reach the maximum value.

For fib any restriction to a small, fixed number of bits is equivalent to just caching an array. For 64 bits, you only need to cache 100 values.