crimsonaluca20

For the code above memory complexity is still O(N) even in a language that optimizes for tail calls. This occurs because you have an additional expression that occurs AFTER your recursive call that means the system must hold everything on the call stack for it to work.

Additionally you have a spelling error on line 5.

>(Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.)

This is not true. The recursive code will not compile with zero overhead even in haskell or lisp.

  fib :: int -> int
  fib 0 = 1
  fib 1 = 1
  fib n = fib (n - 1) + fib (n - 2)

The code above will add layers to the call stack and has a speed complexity of O(N) and memory complexity of O(N).

To optimize in Haskell you need to deliberately restructure your code.

  fib :: int -> int
  fib n = let _fib 0 a b = a
              _fib 1 a b = b
              _fib n a b = fib (n - 1) b (a + b) 
          in _fib n 0 1

The above code will have O(N) speed complexity and constant memory in Haskell. In order for Haskell or any language with tail recursion optimization to work the recursive call must take up the entire return expression. In short the coder must deliberately make optimizations and write recursion in a way similar to the original iterative syntax in order for such tricks to work.