离散数学与证明 I · 递推关系与递归过程
F(n)=F(n-1)+F(n-2)
斐波那契递归树与重复子问题
选择一个 n，观察递归树怎样展开；同一个 F(k) 出现多次时会被高亮，再和自底向上的表格法逐项对照。
递归树
每个圆点是一次函数调用；黄色表示同一个子问题被反复调用。
根问题
重复子问题
只出现一次
自底向上的表格法
从 F(0) 和 F(1) 开始，每个 F(k) 只保留一次，后面的项直接取表中已有结果。
递归树：15 次调用
相同子问题会重新展开。
表格法：6 个表格项
每个 k 只计算并保存一次。