递归函数用于另一个函数进行的递归调用次数（McCarthy 91）

Question

我们有麦卡锡91功能： 我们要解决的问题是写下一个递归T(n)，其中T(n)表示执行M(n)时进行的递归调用次数。

到目前为止我们知道当n > 100 时递归调用的次数为0，当n <=100.

时为2+2(100-n)

Answer 1

我不打算为你做功课，但尝试编写一个程序，而不是只返回 M(n)，返回 M(n) 的结果和递归调用的次数：

def Mx(n):
    """returns M(n) and the number of recursive calls"""
    if n > 100:
        return n - 10, 0
    else:
        a, r0 = Mx(n + 11)
        b, r1 = Mx(a)
        return b, r0 + r1 + 2

在 0..100 范围内的值上运行该程序。您是否看到 M(n) 值的模式？您是否看到递归调用数量的模式？现在证明它。