调用方法两次时尾部(？)递归的说明

Question

我们有以下代码:

import time

def rec1(len):
    if( len < 2): return 1;
    return 2*rec1(len-1);

def rec2(len):
    if( len < 2): return 1;
    return rec2(len-1) + rec2(len-1);

def callAndReport(len, method):
    time1 = time.time()
    answer = method(len)
    time2 = time.time()
    print("{0} with {1}:{2} in {3:.0f} ms".format(len,method.__name__,answer, (time2-time1)*1000))

if __name__ == '__main__':
   callAndReport(20,rec1)
   callAndReport(20,rec2)
   print('')
   callAndReport(23,rec1)
   callAndReport(23,rec2)

此代码生成以下输出:

20 with rec1:524288 in 0 ms
20 with rec2:524288 in 642 ms

23 with rec1:4194304 in 0 ms
23 with rec2:4194304 in 4613 ms

有人可以解释执行时间的差异吗？我想的很少,但我想确定一下.

为了完整性,我遇到的原始问题是下面的方法(可以很容易地表达为for循环,但这不是重点):

def find11s_rec(len):
    if len<2: return 0
    if len== 2: return 1;   
    return find11s_rec(len-2)+find11s_rec(len-1)+2**(len-2)

.

Answer 1

那是因为虽然rec1只使用rec1一次,但rec2使用rec2两次.然后那些内部 rec2呼叫将每次呼叫rec2两次.函数调用的数量将呈指数级增长.虽然rec1可能会使用x电话,但rec2会使用2^x电话.在计算机科学术语中,rec1是O(x)而rec2O(2 ^ x).在更复杂的情况下,危险的递归可能是不明显的; 所以使用调试器找出实际完成的内容.