递归函数

0. 概念

• 形式：函数 A 内部，继续调用 函数 A
• 理解

  1. 回归起始点
  2. 每层传递逻辑
  3. 每层回归值
  

• 示例

  def factory(n):
      if n == 1:
          return 1
      return n * factory(n - 1)
  # n 较大时, 比较耗性能
  result = factory(5)
  print(result)
  

1. 归并排序

• 理解

  1. 将一个无序列表, 进行二分法递归拆分
  2. 分到最细之后, 再对两个有序列表进行排序合并回归
  

• 示例

  def merge(left, right):
      merge_list = []
      i = j = 0
      while i < len(left) and j < len(right):
          if left[i] < right[j]:
              merge_list.append(left[i])
              i += 1
          else:
              merge_list.append(right[j])
              j += 1
      if i == len(left):
          for i in right[j:]:
              merge_list.append(i)
      else:
          for j in left[i:]:
              merge_list.append(j)
      return merge_list
  
  def merge_sort(lists):
      if len(lists) <= 1:
          return lists
      middle = len(lists) // 2
      left = merge_sort(lists[:middle])
      right = merge_sort(lists[middle:])
      return merge(left, right)
  
  print(merge_sort([187, 87, 43, 67, 12, 200, 34, 67]))