以斐波那契 fib(n) 为例,观察递归调用树与每一步返回值。
递归树:将递归调用过程画成树,每个节点代表一次调用,子节点为其递归调用的子问题。
斐波那契:fib(n)=fib(n-1)+fib(n-2),fib(0)=0,fib(1)=1。递归树中同一层可能有多处相同 fib(k),体现重复计算。