[lmkg]

Take a look at the recursive code being used, it's not exactly what you think it is. The naive recursive solution makes two recursive calls to the Fib function, and requires an exponential number of calls. The 'standard' recursive solution defines a helper function that takes two arguments, so each recursive step only takes one function call and the total number of calls is linear.

In general, a recursive solution need never have a bigger big-O than an iterative solution. You just need to define a helper function that has a many input parameters as your for-loop had variables that it updates.