动态规划与递归的区别是什么？以斐波那契数列为例详解

Hey there! I totally get where you're coming from—when you first wrap your head around these concepts, it's super easy to blur the lines between recursion and dynamic programming, especially since DP often leverages recursion in some form. Let's unpack this clearly using the Fibonacci sequence as our example.

First, Let's Recap the Fibonacci Problem #

The nth Fibonacci number is defined as:

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) for n ≥ 2

1. Plain Recursion: The "Naive" Approach #

Let's start with a basic recursive implementation. Here's what it looks like in Python:

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

What's the Issue Here? #

Recursion works by breaking the problem into smaller subproblems, but it doesn't remember the results of those subproblems. For example, if we calculate fib_recursive(5):

• We need fib_recursive(4) and fib_recursive(3)
• fib_recursive(4) needs fib_recursive(3) and fib_recursive(2)
• Now fib_recursive(3) is being calculated twice—once for fib_recursive(5) and once for fib_recursive(4)
• As n grows, this repetition explodes. The time complexity here is O(2ⁿ)—exponential, which is terrible for large n (try n=40, it'll take noticeable time).
• We also have stack overflow risks for very large n, since each recursive call adds to the call stack.

2. Dynamic Programming: Fixing the Repetition #

Dynamic programming (DP) is all about storing the results of subproblems so we don't have to recompute them. There are two main flavors:

A. Top-Down DP (Memoized Recursion) #

This is recursion with a cache (or "memo") to store already computed results. Let's adjust our recursive function:

def fib_memoized(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memoized(n-1, memo) + fib_memoized(n-2, memo)
    return memo[n]

What's Different? #

• We use a memo dictionary to save every Fibonacci number we calculate. The first time we compute fib_memoized(3), we store it. Next time we need it, we just look it up in O(1) time.
• Time complexity drops to O(n)—linear, since we only compute each F(k) once for k from 0 to n.
• Space complexity is O(n) (for the memo and the call stack).

B. Bottom-Up DP (Iterative Approach) #

Instead of starting from n and working down to 0, we start from the base cases and build up to n. This avoids the call stack entirely:

def fib_bottom_up(n):
    if n <= 1:
        return n
    prev_prev = 0  # F(0)
    prev = 1       # F(1)
    for i in range(2, n+1):
        current = prev_prev + prev
        prev_prev = prev
        prev = current
    return prev

What's Different Here? #

• We don't use recursion at all. We just iterate from 2 to n, keeping track of the last two Fibonacci numbers.
• Time complexity is still O(n), but space complexity is optimized to O(1)—we only need two variables to store previous values, no memo or call stack overhead.
• This is often the preferred approach for DP problems when possible, as it's more efficient in terms of space.

Key Differences at a Glance #

Let's summarize the core distinctions using our Fibonacci example:

• Core Idea:
  • Recursion is about splitting a problem into smaller subproblems and solving them recursively (no concern for repetition).
  • Dynamic programming is about optimizing recursive solutions by eliminating redundant subproblem calculations—it's recursion + memoization (or iterative building).
• Efficiency:
  • Plain recursion has exponential time complexity (O(2ⁿ)) for Fibonacci.
  • DP (both flavors) has linear time complexity (O(n)).
• Space:
  • Plain recursion uses O(n) stack space (and no extra storage for subproblems).
  • Top-down DP uses O(n) stack space + O(n) memo space.
  • Bottom-up DP uses O(1) space (no stack, no memo).
• Control:
  • Recursion relies on the call stack to handle subproblem order.
  • Bottom-up DP lets you explicitly control the order of solving subproblems, which can lead to further optimizations.

Final Thought #

Recursion is a tool for breaking down problems, while dynamic programming is a technique for optimizing those recursive solutions (or building iterative ones) by reusing work you've already done. The Fibonacci sequence is a classic example because it makes the redundant calculations in plain recursion so obvious—once you see how much time you save with DP, the difference clicks.

内容的提问来源于stack exchange，提问作者Anonymous