(二)递归
递归需要满足三个条件:
(1)一个问题的解可以分解成几个子问题的解
(2)这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
(3)存在递归终止条件
写递归代码的关键也是,找到递推公式和终止条件
案例1 阶乘
#循环实现
#时间O(n)
#空间O(1)
def factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result
#递归实现
#时间O(n)
#空间O(n)
ef factorial_recursive(n):
if n == 1:
return 1
return n * factorial_recursive(n - 1)
案例2 斐波那契数列
#递归实现
#时间O(2^n)
def fibonacci1(n):
assert(n>0)
if (n <= 2):
return 1
return fibonacci2(n-1) + fibonacci2(n-2)
#循环实现
#时间O(n)
def fibonacci2(n):
assert(n>0)
a,b=0,1
for i in range(1,n+1):
a,b=b,a+b
return a
def fibonacci3(n):
assert(n>0)
if (n <= 1):
return (n,0)
(a, b) = fibonacci3(n-1)
return (a+b, a)
案例3 打印尺子
(热身)打印一下内容:
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
#时间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
画尺子:
#画横线
def draw_line(tick_length, tick_label=‘‘):
line = ‘-‘ * tick_length
if tick_label:
line += ‘ ‘ + tick_label
print(line)
#画每一个大格子
def draw_interval(center_length):
if center_length > 0:
draw_interval(center_length - 1)
draw_line(center_length)
draw_interval(center_length - 1)
#画多个格子
def draw_rule(num_inches, major_length):
draw_line(major_length, ‘0‘)
for j in range(1, 1 + num_inches):
draw_interval(major_length - 1)
draw_line(major_length, str(j))
案例4 数字表达式
Given two integers a ≤ b, write a program that transforms a into b by a minimum sequence of increment (add 1) and unfolding (multiply by 2) operations.
For example,
23 = ((5 * 2 + 1) * 2 + 1)
113 = ((((11 + 1) + 1) + 1) * 2 * 2 * 2 + 1)
def intSeq(a, b):
if (a == b):
return str(a)
if (b % 2 == 1):
return "(" + intSeq(a, b-1) + " + 1)"
if (b < a * 2):
return "(" + intSeq(a, b-1) + " + 1)"
return intSeq(a, b/2) + " * 2";
案例5 汉诺塔
def hanoi(n, start, end, by):
if (n==1):
print("Move from " + start + " to " + end)
else:
hanoi(n-1, start, by, end)
hanoi(1, start, end, by)
hanoi(n-1, by, end, start)
原文:https://www.cnblogs.com/gdy1993/p/12984699.html