尾部说明（？）调用方法twi时的递归

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的复杂度为O（n），rec2的复杂度为O（2^n）。这是一个很大的性能差异。你知道吗

rec2(n) = rec2(n-1) + rec2(n-1)
        = (rec2(n-2) + rec2(n-2)) + (rec2(n-2) + rec2(n-2)) = 4 * rec2(n-2)
          ...

rec2(n) = (2^n)*rec2(1)
        = O(2^n)