Data Structures and Algorithms Basics（002）: Recursion
Data Structures and Algorithms Basics（002）: Recursion
用户5473628
发布于 2019-08-08 14:55:01
发布于 2019-08-08 14:55:01
目录：
一、Recursion理解(7)
二、练习题(10)
递归：
递归循环要比for循环占用更多的空间复杂度:
For循环时间复杂度是O（n），空间复杂度是O（1）；
递归循环的时间复杂度和空间复杂度都是O（n）;
所以递归循环要占用更多的内存空间（stack空间）。
一、Recursion理解
1 求和
2 阶乘
3 斐波那契数列
4 打印尺子
5 数学表达式
6 汉诺塔
7 格雷码
# 1，求和：使用循环算法
def sum_recursion(n):
if n == 0:
return 0
return n + sum_recursion(n-1)
if __name__ == '__main__':
print(sum_recursion(10))
# 2，阶乘：
def factorial(n):
if n == 1:
return 1
return n * factorial(n-1)
if __name__ == '__main__':
print(factorial(10))
# 3,斐波那契数列：
def fibonacci_first(n):
assert(n >= 0)
a, b = 0, 1
for i in range(1, n+1):
a, b = b, a+b
return a
def fibonacci_second(n):
assert(n>=0)
if (n <= 2):
return 1
return fibonacci_second(n-1) + fibonacci_second(n -2)
def fibonacci_third(n):
assert(n >= 0)
if (n <= 1):
return(n, 0)
(a, b) = fibonacci_third(n-1)
return (a+b, a)
def fibonacci(n):
assert(n>=1)
result = [1, 1]
for i in range(2, n):
result.append(result[-2] + result[-1])
return result
if __name__ == '__main__':
# time fibonacci_first(20)
# time fibonacci_second(20)
# time fibonacci_third(20)
import time
start = time.time()
print(fibonacci_first(20))
end = time.time()
print('fibonacci_first cost time: {:.16f} s.'.format(end - start))
start = time.time()
print(fibonacci_second(20))
end = time.time()
print('fibonacci_second cost time: {:.16f} s.'.format(end - start))
start = time.time()
print(fibonacci_third(20))
end = time.time()
print('fibonacci_third cost time: {:.16f} s.'.format(end - start))
print(fibonacci(20))
print('黄金分割率：{:.16f}.'.format(fibonacci(20)[-1]/fibonacci(20)[-2]))
# 尺子：
def ruler_recursion(n):
assert(n>=0)
if n == 1:
return '1'
t = ruler_recursion(n-1)
return t + ' ' + str(n) + ' ' + t
def ruler_for(n):
result = ''
for i in range(1, n+1):
result = result + str(i) + ' ' + result
return result
class ruler_print(object):
def draw_line(self, tick_length, tick_label=''):
line = '-' * tick_length
if tick_label:
line += ' ' + tick_label
print(line)
def draw_interval(self, center_length):
if center_length > 0:
self.draw_interval(center_length - 1)
self.draw_line(center_length)
self.draw_interval(center_length - 1)
def draw_rule(self, num_inches, major_length):
self.draw_line(major_length, '0')
for j in range(1, 1 + num_inches):
self.draw_interval(major_length - 1)
self.draw_line(major_length, str(j))
if __name__ == '__main__':
print(ruler_recursion(5))
print(ruler_for(5))
my_ruler = ruler_print()
r = my_ruler.draw_rule(3,5)
print(r)
# 5, 数学表达式：
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";
if __name__ == '__main__':
a = 5;
b = 101;
print(str(b) + " = " + intSeq(a, b))
# 6，汉诺塔：
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)
if __name__ == '__main__':
print(hanoi(5, 'start', 'end', 'by'))
# 7, 格雷码：
def moves_ins(n, forward):
if n == 0:
return
moves_ins(n-1, True)
print("enter ", n) if forward else print("exit ", n)
moves_ins(n-1, False)
if __name__ == '__main__':
print(moves_ins(3, True))二、练习题:
1,子集：回溯法；
2，子集：包含重复元素的集合，求所有可能的子集组合。注意：子集个数比不重复的集合要少；
3, 排列组合；
4, 排列组合：包含重复元素的集合，求所有可能的排列组合。注意：组合个数要少于重复的集合；
5, 排列组合：从n个元素中有序选择k个元素；
6, 排列组合：按指定字母排序；
7, 查找总和等于指定数字的子集；
8, 查找总和等于指定数字的子集: 原集合含有重复元素；
9, 寻找所有符合语法的n组括号的组合；
10, 八皇后问题。
# 1,子集：回溯法
class subsets1_BackTracking(object):
def subsets_recursive(self, nums):
lst = []
result = []
self.subsets_recursive_helper(result, lst, nums, 0);
return result;
def subsets_recursive_helper(self, result, lst, nums, pos):
result.append(lst[:])
for i in range(pos, len(nums)):
lst.append(nums[i])
self.subsets_recursive_helper(result, lst, nums, i+1)
lst.pop()
def subsets2_recursion(nums):
res = [[]]
for num in nums:
res += [i + [num] for i in res]
return res
def subsets3_for(nums):
result = [[]]
for num in nums:
for element in result[:]:
x=element[:]
x.append(num)
result.append(x)
return result
if __name__ == '__main__':
nums = [1, 2, 3]
sub = subsets1_BackTracking()
print(sub.subsets_recursive(nums))
# 2，子集：包含重复元素的集合，求所有可能的子集组合。注意：子集个数比不重复的集合要少。
def subsets2(nums):
res = [[]]
for num in nums:
res += [ i + [num] for i in res if i + [num] not in res]
return res
class subsets2_BackTracking(object):
def subsets_recursive2(self, nums):
lst = []
result = []
nums.sort()
#print(nums)
self.subsets2_recursive_helper(result, lst, nums, 0);
return result;
def subsets2_recursive_helper(self, result, lst, nums, pos):
result.append(lst[:])
for i in range(pos, len(nums)):
if (i != pos and nums[i] == nums[i-1]):
continue;
lst.append(nums[i])
self.subsets2_recursive_helper(result, lst, nums, i+1)
lst.pop()
if __name__ == '__main__':
nums = [1,2,2]
print(subsets2(nums))
sub = subsets2_BackTracking()
print(sub.subsets_recursive2(nums))
# 3, 排列组合：
def permutation1_recursion(result, nums):
if (len(nums)==0):
print(result)
for i in range(len(nums)):
permutation1_recursion(result+str(nums[i]), nums[0:i]+nums[i+1:]) #
def permutation2(nums):
perms = [[]]
for n in nums:
new_perms = []
for perm in perms:
for i in range(len(perm)+1):
new_perms.append(perm[:i] + [n] + perm[i:]) # insert n
perms = new_perms
return perms
if __name__ == '__main__':
nums = [1, 2, 3]
print(permutation1_recursion('', nums))
print(permutation2(nums))
# 4, 排列组合：包含重复元素的集合，求所有可能的排列组合。注意：组合个数要少于重复的集合。
def permUnique1_recursion(result, nums):
nums.sort()
if (len(nums)==0):
print(result)
for i in range(len(nums)):
if (i != 0 and nums[i] == nums[i-1]):
continue;
permUnique1_recursion(result+str(nums[i]), nums[0:i]+nums[i+1:])
def permuteUnique2_for(nums):
ans = [[]]
for n in nums:
new_ans = []
for l in ans:
for i in range(len(l)+1):
new_ans.append(l[:i]+[n]+l[i:])
if i<len(l) and l[i]==n: break #handles duplication
ans = new_ans
return ans
if __name__ == '__main__':
nums = [6, 8, 6]
permUnique1_recursion('', nums)
print(permuteUnique2_for(nums))
# 5, 排列组合：从n个元素中有序选择k个元素。
def permSizeK_recursion(result, nums, k):
if k == 0:
print(result)
for i in range(len(nums)):
permSizeK_recursion(result+str(nums[i]), nums[0:i] + nums[i+1:], k - 1)
if __name__ == '__main__':
nums = [1, 2, 3, 4]
permSizeK_recursion('', nums, 2)
# 6, 排列组合：word = “medium-one”，Rule = “io”，solutions = [“medium-one”, “medIum-one”, “medium-One”, “medIum-One”]
class permutation_letter(object):
def __init__(self):
self.results = set()
self.keys = set()
def permLetter(self, word, rule):
rule = rule.lower()
for c in rule:
self.keys.add(c)
self.permHelper(word, rule, 0, "")
def permHelper(self, word, rule, index, prefix):
length = len(word)
for i in range(index, length):
c = word[i]
if (c in self.keys):
self.permHelper(word, rule, i + 1, prefix + c)
c = c.upper()
self.permHelper(word, rule, i + 1, prefix + c)
else:
prefix += c
if (len(prefix) == len(word)):
self.results.add(prefix)
if __name__ == '__main__':
word = "helloworld"
per_letter = permutation_letter()
per_letter.permLetter(word, 'hd')
print(per_letter.results)
# 7, 查找总和等于指定数字的子集:
class subsets_sum(object):
def combination(self, nums, t):
result = []
tmp = []
self.combHelper(result, tmp, nums, t, 0)
return result
def combHelper(self, result, tmp, nums, remains, start):
if remains < 0: return
if remains == 0:
result.append(tmp[:])
else:
for i in range(start, len(nums)):
tmp.append(nums[i])
self.combHelper(result, tmp, nums, remains - nums[i], i)
tmp.pop()
if __name__ == '__main__':
candidates = [2,3,5]
sub_sum = subsets_sum()
print(sub_sum.combination(candidates, 8))
# 8, 查找总和等于指定数字的子集: 原集合含有重复元素。
class subsets_sum2(object):
def combination2(self, nums, t):
result = []
tmp = []
nums.sort()
self.combHelper2(result, tmp, nums, t, 0)
return result
def combHelper2(self, result, tmp, nums, remains, start):
if remains < 0: return
if remains == 0:
result.append(tmp[:])
else:
for i in range(start, len(nums)):
if(i > start and nums[i] == nums[i-1]): continue; # skip duplicates
tmp.append(nums[i])
self.combHelper2(result, tmp, nums, remains - nums[i], i + 1)
tmp.pop()
if __name__ == '__main__':
candidates = [2,5,2,1,2]
sub_sum2 = subsets_sum2()
print(sub_sum2.combination2(candidates, 5))
# 9, 寻找所有符合语法的n组括号的组合：
def generateParenthesis(n):
def generate(prefix, left, right, parens=[]):
if right == 0: parens.append(prefix)
if left > 0: generate(prefix + '(', left-1, right)
if right > left: generate(prefix + ')', left, right-1)
return parens
return generate('', n, n)
if __name__ == '__main__':
print(generateParenthesis(5))
# 10, 八皇后问题:
class eight_Queens(object):
def solveNQueens(self, n):
res = []
self.dfs([-1]*n, 0, [], res)
return res
# nums is a one-dimension array, like [1, 3, 0, 2] means
# first queen is placed in column 1, second queen is placed
# in column 3, etc.
def dfs(self, nums, index, path, res):
if index == len(nums):
res.append(path)
return # backtracking
for i in range(len(nums)):
nums[index] = i
if self.valid(nums, index): # pruning
tmp = "." * len(nums)
self.dfs(nums, index+1, path + [tmp[:i]+"Q"+tmp[i+1:]], res)
# check whether nth queen can be placed in that column
def valid(self, nums, n):
for i in range(n):
if abs(nums[i]-nums[n]) == n - i or nums[i] == nums[n]:
return False
return True
if __name__ == '__main__':
game = eight_Queens()
print(game.solveNQueens(8))本文参与?腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-04-23，如有侵权请联系?cloudcommunity@tencent.com 删除
本文分享自 MiningAlgorithms 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与?腾讯云自媒体同步曝光计划? ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读