News for hackers. Stuff that matters.
Re:On calculating Fibonacci numbers in C by lmkg on Monday January 28, 2013 @04:23PM (#5130743)
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.

There are no comments on this comment yet.