交互式Python实验室

Fibonacci (Recursive)

Playground在加载时自动运行。点击运行我的代码来追踪你的Python代码 — 每一步实时动画展示。

解释·逐行

回放·逐步

挑战·引导式提示

XP·...

数据流水线

advanced 路径

Bubble Sort

Two Sum

Valid Parentheses

Merge Sort

Quick Sort

Heap Sort

Breadth-First Search

Depth-First Search

Binary Tree Traversal

Fibonacci (Recursive)

解释

Line 1

fib(8): naive recursion. Will make ~2^8 = 256 function calls.

为什么用这种方法？

Naive fib has no memory of previous results. fib(8) calls fib(7) and fib(6). fib(7) calls fib(6) again. fib(6) is computed many times — this exponential blowup makes it impractical for n > 40.

Structured Explanation

Overview

递归斐波那契: f(n)=f(n-1)+f(n-2)。简单但指数级时间，需要记忆化。

Analogy

就像家谱——每个人从父母获取信息。

Step-by-step

基础情况: f(0)=0, f(1)=1
否则: return f(n-1)+f(n-2)
这是O(2^n)——非常慢
用@lru_cache改进到O(n)

Visual

fib(4) ├─fib(3) fib(2) │ ├─fib(2) fib(1) ├─fib(1) fib(0)

Common mistakes

无记忆化时对大n使用
基础情况不正确处理0或负数

Practice questions

用@functools.lru_cache装饰fib()
比较无记忆化/有记忆化/迭代的时间

Time

O(2^n)无记忆化，O(n)有记忆化

Space

O(n)

复杂度

时间

O(2ⁿ) naive / O(n) memoized

空间

O(n)

复杂度概览

O(1)

O(log n)

O(n)时间空间

O(n log n)

O(n²)

n = 8范围 1-20

当 N = 8 时

复杂度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

挑战

实现递归斐波那契。检查fib(10)和fib(35)。注意时间差异。

提示

通过字典缓存添加记忆化。调用树从2^n降至n，效果显著。

代码工作室

Fibonacci (Recursive)

Monaco就绪

Python就绪

lesson.pyline 1

Loading editor...

输出控制台

0 lines

暂无输出...

现实世界应用

1

Teaching how easily systems crash

2

Why caching architectures exist

3

Stress-testing recursion constraints

Comments

Loading comments...