Recursion

Recursive functions have a very curious aura around them, for me personally it was always interesting to try and find a non-recursive version for functions defined recursively. I used to solve questions of that nature in previous math courses, yet here it seems the point is in sticking with recursion and trying to handle it as it is.

I must admit that I actually spent some time with paper trying to come up with a non-recursive formula for the Fibonacci numbers. When that did not work, I tried google. I guess there really is no way of doing that at this time, but is there an actual proof that Fibonacci sequence cannot be defined without recursion?

That aside, one lesson learned from this past lecture was that working with recursion and finding more efficient ways of handling it requires a lot of patience, which may or may not pay off (looking for a non-recursive Fibonacci formula did not pay off). 

Working with time complexity seemed like a much easier task after that, despite random confusion about which expression should be greater or smaller than the other. If that is going to be on the test, then I suppose we need to remember which of the Θ, Ω and O are which, but hopefully their definitions will be provided.