面试题：Python控制流在递归与动态规划中的应用

Question

实现一个函数，计算第n个斐波那契数。要求使用Python控制流语句，通过递归和动态规划两种方式实现，并分析两种实现方式在时间复杂度和空间复杂度上的差异。同时，说明在实际应用中，何时选择递归方式，何时选择动态规划方式。

Answer 1

递归方式

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

• 时间复杂度：$O(2^n)$，因为每次递归调用会产生两个新的递归调用，形成指数级增长。
• 空间复杂度：$O(n)$，递归调用栈的深度最大为n。

动态规划方式

def fibonacci_dynamic(n):
    if n <= 1:
        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]

• 时间复杂度：$O(n)$，因为只需遍历一次计算到第n项。
• 空间复杂度：$O(n)$，用于存储中间结果的数组长度为n + 1。优化后空间复杂度可降为$O(1)$，只需保存最近的两个数。

选择建议

• 递归方式：适用于问题规模小，代码简洁性优先，并且不担心性能损耗的场景，如教学演示等。
• 动态规划方式：适用于问题规模较大，对时间复杂度要求较高，追求高效性能的实际应用场景，如大规模数据计算等。