求表示McCarthy 91函数M(n)递归调用次数的递归式T(n)

首先明确McCarthy 91函数的定义：

M(n) = 
    n - 10,  当 n > 100
    M(M(n + 11)), 当 n ≤ 100

其中T(n)表示计算M(n)过程中产生的递归调用次数（不含初始调用M(n)本身），分三种情况推导递归式：

情况1：n > 100 #

此时M(n)直接返回n-10，没有触发任何递归调用，因此：
T(n) = 0

情况2：90 ≤ n ≤ 100 #

此时n+11 > 100，所以M(n+11) = (n+11)-10 = n+1。计算M(n)时，会先递归调用M(n+11)（1次调用，且该调用无内部递归），再递归调用M(n+1)（1次调用），加上计算M(n+1)产生的递归次数T(n+1)，因此递归式为：
T(n) = T(n+1) + 2

情况3：n ≤ 89 #

此时n+11 ≤ 100，根据McCarthy 91函数的性质，M(n+11) = 91。计算M(n)时，会先递归调用M(n+11)（1次调用，对应递归次数T(n+11)），再递归调用M(91)（1次调用，对应递归次数T(91)）。

通过情况2的递推可计算得T(91)=20（从T(100)=2开始，每次n减1时T(n)加2，共9次递推：2 + 2*9=20），因此该情况的递归式为：
T(n) = T(n+11) + 22

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