为含多分支返回语句的递归函数推导递推关系式

首先注意到代码里的color参数其实不影响递归分支的选择——它只是在递归调用中传递，但当前函数的逻辑判断只依赖has_blue_plate。所以我们可以用两个状态变量来简化问题：

• A(n)：堆叠n个盘子，且堆叠中已经包含蓝盘的总方式数（对应stack_plates(n, *, True)的返回值）
• B(n)：堆叠n个盘子，且堆叠中完全没有蓝盘的总方式数（对应stack_plates(n, *, False)的返回值）

1. 推导A(n)的递推式 #

当has_blue_plate=True时，代码的返回逻辑是：

return stack_plates(n-1, 'Blue', True) + stack_plates(n-1, 'Green', False)

• 第一个递归调用stack_plates(n-1, 'Blue', True)：n-1个盘子且已有蓝盘，对应A(n-1)
• 第二个递归调用stack_plates(n-1, 'Green', False)：n-1个盘子且无蓝盘，对应B(n-1)
  所以：
  A(n) = A(n-1) + B(n-1)

2. 推导B(n)的递推式 #

当has_blue_plate=False时，代码的返回逻辑是：

return stack_plates(n-1, 'Red', False) + stack_plates(n-1, 'Blue', True) + stack_plates(n-1, 'Green', False)

• 第一个和第三个调用都是n-1个盘子且无蓝盘，各对应B(n-1)
• 第二个调用是n-1个盘子且已有蓝盘，对应A(n-1)
  所以合并后：
  B(n) = A(n-1) + 2*B(n-1)

3. 初始条件 #

当n=0时，函数直接返回1，所以：
A(0) = 1，B(0) = 1

可选：合并为总方式数的递推式 #

如果设总方式数T(n) = A(n) + B(n)，代入上面的式子可以得到：

T(n) = A(n) + B(n)
     = [A(n-1)+B(n-1)] + [A(n-1)+2B(n-1)]
     = 2A(n-1) + 3B(n-1)
     = A(n-1) + 2*T(n-1)

或者进一步用T(n-1)替换A(n-1)（因为A(n-1) = T(n-1) - B(n-1)），不过通常保留A(n)和B(n)的递推式更直观。

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