包含递归和两个内部for循环的增长顺序

Question

我试过下面的问题，但我不确定我是否正确。我已经得出结论，它是一个n^2函数的大θ。我的推理是i和j的内部2个循环相当于一个操作序列，0、1、2、3、4、5….x-1，可以通过算术运算转换成（x*x-1）/2。但是，外部递归调用有点让我绊倒了。我很想把外部递归调用看作是另一个while循环，但我把它打退了，因为它不是另一个while循环或for循环，因为x也会改变。有人能帮我更好地理解下面的问题吗？在

    def foo(x):
        if x < 1: 
            return 'boo'
        for i in range(x): 
            for j in range(i):
                return foo(i + j)
        return foo(x-1)

修订版：我刚刚在python解释器中运行了这段代码，结果发现这是一个固定时间，因为这是一个技巧问题。原因是，return语句只计算foo（1），然后不管n的大小，都会输出“boo”。在

但是--->；如果我将我的代码改为以下代码呢。运行时间现在是θ（n^2）还是θ（n^3）？在

^{pr2}$

Answer 1

编辑：首先有i+i的问题，但现在有了{}，所以现在我的答案是错误的。在

---

当x < 1它会打印“boo”—没有什么有趣的。在

当x >= 1时，你可以到达循环

for i in range(x): 
    for j in range(i):
        return foo(i+i)

所以让x = 1你就有了

^{pr2}$

所以让i = 0-然后你

    for j in range(0):

它将更新运行

所以让i = 1-然后你

    for j in range(1):

对于j = 0，您可以运行

    return foo(2)

然后回到这个描述的开头。
你将再次得到return foo(2)。你自己查一下。在

所以对于'x>；=1'，你总是得到return foo(2)。
所以你可以把代码减少到

def foo(x):
    if x < 1: 
        return 'boo'
    return foo(2)

（您将永远无法到达return foo(x-1)）

你有无穷的功能。在

（希望我是对的）