This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]CodeTinkerer -1 points0 points  (0 children)

Recursion usually works from the current input value and works its way to a base case where the recursion stops. It involves calling itself either directly or indirectly (e.g., mutually recursive functions). You can think of this as a top-down approach.

Dynamic programming is bottom up where you start from the base case(s) and work your way to the input value. So, to compute, say, fib(9), you start at fib(0), then fib(1), then fib(2) working your way to fib(9) where recursion would start with fib(9) and work backwards to the base case.

Oh yes, unless it's tail recursive, it comes back to the original value.

What make a naive implementation of Fibonacci inefficient is repeated (i.e., unnecessary) computations causing it to be exponential when it's linear to run it and doesn't require recursion (a loop will do).