Dynamic programming: recursion+memoization vs loop+list

Question

The documentation for @functools.lru_cache provides an example of computing Fibonacci numbers using a cache to implement a dynamic programming technique:

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

I've seen this approach used for solving various programming puzzles. Does it have the same time/space complexity as the 'standard' iterative dynamic programming approach, e.g.:

def fib(n):
    if n < 2:
        return n
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(2 , n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Also, are there any downsides to using the recursive approach?

MBo · Accepted Answer · 2018-12-12 10:17:28Z

3

It should have the same complexity as memoization (top-down) kind of dynamic programming.

Iterative method with step-by-step table filling (bottom-up dynamic programming) might have slightly different complexity, because memoization remembers only parameter sets, needed to build final solution

This difference is not important for fibbonacci or factorial examples, but might happen for tasks with sparse subproblem table (when it's hard to predict what entries will be used later)

edited Dec 12, 2018 at 10:17

answered Dec 12, 2018 at 10:12

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Will Ness Over a year ago

so if memoized space is sparse, iterative should be worse than top-down.

MSeifert · Accepted Answer · 2018-12-12 10:23:05Z

The following compares the functions you've shown. In general these observations don't necessarily hold for any recursive or iterative approach for calculating the Fibonacci numbers but only the implementations you've shown in the question.

Time complexity:

First call

Recursive approach: O(n)
Iterative approach: O(n)

Subsequent calls

Recursive approach: O(1)
Iterative approach: O(n)

Constant factors

The constant factors might be completely different. It's likely (first call) that the iterative approach will be faster than the recursive approach even though both are O(n). This is just a guess, based on my experience (not actual tests) that list indexing is much faster than calling a function.

Memory complexity:

Both require O(n) additional memory, however the recursive approach will keep the memory (so it's permanently allocated) while the iterative approach will free the memory after the function completed.

Other differences

The recursion limit of Python. When the time gets too big and the cache isn't filled then the recursive approach will fail because of that limit, for example fib(500). There is no such limit (except when you run out of memory) for list indexing.

Collectives™ on Stack Overflow

Dynamic programming: recursion+memoization vs loop+list

2 Answers 2

1 Comment

Time complexity:

First call

Subsequent calls

Constant factors

Memory complexity:

Other differences

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Time complexity:

First call

Subsequent calls

Constant factors

Memory complexity:

Other differences

Comments

Your Answer

Sign up or log in

Post as a guest

Related