练习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
分析
- 第一个代码的时间复杂度是O(2^n)，它不会保存ruler(n-1)的运算结果，所以需要重复计算。
- 第三种代码用循环实现，循环内部有f(n)=g(f(n))，这样的循环可以用递归形式实现。
网友评论