Why go down this rabbit hole when we already had an iterative version that worked for the Fibonacci sequence? Well, I'll come clean—this is all an excuse to gripe that CPython does not do this kind of tail-call optimization automatically. The tail_call_fib function here, if it were in a language like Haskell or Scheme, would be automatically rewritten into something very similar to the DP solution, but it isn't here. If you're working in a compiled language, sometimes you can even get smarter than that and automatically rewrite functions into a tail-call-recursive equivalent. In Haskell, this function won't stack overflow:

fact 0 = 1
fact n = n * fact (n - 1)

Haskell can see that this can be rewritten into a tail-call-recursive form and then rewritten into a loop. Pretty cool, huh?

On the side we have what tail call recursion for the Fibonacci sequence would look like. Hopefully the comparison between the iterative and recursive solutions shows how similar they really are.

Code
Output
True

Why go down this rabbit hole when we already had an iterative version that worked for the Fibonacci sequence? Well, I'll come clean—this is all an excuse to gripe that CPython does not do this kind of tail-call optimization automatically. The tail_call_fib function here, if it were in a language like Haskell or Scheme, would be automatically rewritten into something very similar to the DP solution, but it isn't here. If you're working in a compiled language, sometimes you can even get smarter than that and automatically rewrite functions into a tail-call-recursive equivalent. In Haskell, this function won't stack overflow:

fact 0 = 1
fact n = n * fact (n - 1)

Haskell can see that this can be rewritten into a tail-call-recursive form and then rewritten into a loop. Pretty cool, huh?

On the side we have what tail call recursion for the Fibonacci sequence would look like. Hopefully the comparison between the iterative and recursive solutions shows how similar they really are.

Code
Output
True