练习1：打印尺子

题目要求

1

1 2 1

1 2 1 3 1 2 1

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

分析

f(n+1)的执行结果由f(n)的执行结果构成，且构成方式与n无关。实现递归在于实现这个构成方式。

代码

#O(2^n)
def ruler_bad(n):
    assert(n>=0)
    if (n==1):
        return "1"
    return ruler(n-1) + " " + str(n) + " " + ruler(n-1)

#O(n)
def ruler(n):
    assert(n>=0)
    if (n==1):
        return "1"
    t = ruler(n-1)
    return t + " " + str(n) + " " + t

def ruler2(n):
    result = ""
    for i in range(1, n+1):
        result = result + str(i) + " " + result
    return result

分析

1. 第一个代码的时间复杂度是O(2^n)，它不会保存ruler(n-1)的运算结果，所以需要重复计算。
2. 第三种代码用循环实现，循环内部有f(n)=g(f(n))，这样的循环可以用递归形式实现。

Tips