By the way they discuss the implementation. First level is ensuring that base cases are covered (i.e. correct implementation of recursion)

Second level is how they explain the simple recursion that’ll hit stack limits (i.e. without tail recursion)

Third level is using accumulator/tail recursion.

See how they can express these ideas and are they able to effectively communicate their intentions.

In my decades of programming I've never had to seriously consider these issues. I have used recursion and have written some pretty deep stuff like cryptography and writing my own interpreter (for a business - not a school project). I've even implemented recursion in a language that didn't support it. I have read about tail recursion several times. I still barely remember what it is. But I know a few books to reach for if I had to use recursion again. This is why the interview process is broken. I've written lots of production code and end up being seen as a lead programmer within weeks of a new job. And your questions would make me look like I don't know what I'm talking about.

Serious request, as a developer who would probably code a naive Fibonacci that doesn't meet your standard: Could you provide a code sample that does meet your standard? This looks like an important learning opportunity for me. Thanks.

Instead of recursing twice, recurse once, by carrying around not fib(n-1) but the pair (fib(n-2), fib(n-1)).

True, but then the "worker" fib() method should be called fib_calculate() and should be wrapped by fib() which then returns a single integer. I believe that breaks the spirit of the question.

Really it's about this type of discussion. Already with your 'but then' you are showing that you know your way around a program.

I'd still have you write the full thing out, but I'm guessing you'd do just fine.

I'd use `go`, by ancient Haskell law and custom ;)

There should be a fourth level where they use the closed form solution to get to the solution they want without any recursion or looping for reasonable values of N. Maybe even a fifth level using the O(log(N)) matrix exponentiation method.

I’m a bit puzzled at the idea of using recursion for an infinite sequence (did OP mean factorial?). Give me a LazyList / generator / IEnumerable instead any day for Fib.

It's easy to memorise all those too without necessarily understanding them.

I think it's the O(log n) algorithm that uses matrix exponentiation to find out the n'th Fibonacci number.