>(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.
Though GHC is sometimes able to do some simple transformations on its own. But not in this case.
For anyone trying this at home: I suggest calculating your additions modulo some constant, so that the numbers involved stay within a fixed size. (Otherwise, you either hit the limits of Int and weird things can happen, or when calculating with the arbitrary precision type Integer, your numbers themselves will grow linearly in space.)
This is not true. The recursive code will not compile with zero overhead even in haskell or lisp.
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.
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.