数学归纳法与递归

什么是数学归纳法

数学归纳法一般步骤是这样的：

• 证明基本情况（通常是n=1)是否成立
• 假设n = k-1成立，再证明n=k也是成立的（k为任意大于1的自然数）

和使用迭代法的计算相比，数学归纳法的最大的特点在于“归纳”二字。它已经总结出了规律。只要我们能够证明这个规律是正确的，就没有必要进行逐步的失算，可能节省很多的时间和资源。

递归调用和数学归纳的逻辑是一样的

只要数学归纳证明的逻辑是对的，递归调用的逻辑就是对的，没有必要纠结递归函数是如何嵌套调用和返回的。

如何把复杂的问题简单化

将复杂的问题，每次都解决一点点，并将剩下的任务转化成为更简单的问题等待下次求解，如此反复，直到最简单的形式。
1.假设n=k-1的时候，问题已经解决（或者已经找到解）。那么只要求解n=k的时候，问题如何解决（或者解是多少）;
2.初始状态，就是n=1的时候，问题如何解决

问题：总金额10元，从[1,2,5,10]中选取数字有多少种组合

rewards = [1, 2, 5, 10]
def get(total_reward, result):
    if total_reward == 0:
        print(result)
    elif total_reward < 0:
        return;
    else:
        for i in rewards:
            new_rst = result.copy()
            new_rst.append(i)
            get(total_reward - i, new_rst) # 递归

最终，结果

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 1, 1, 2, 1]
[1, 1, 1, 1, 1, 1, 2, 1, 1]
[1, 1, 1, 1, 1, 1, 2, 2]
...
[5, 5]
[10]

递归和循环其实都是迭代法的实现，而且在某些场合下，它们的实现是可以相互转化的。

• 递归的核心思想和数学归纳法类似，并更具有广泛性
  1. 一个当前所采取的步骤
  2. 另一个更简单的问题
• 递归会使用计算机的函数嵌套调用。而函数调用本身，就可以保存很多中间状态和变量值，因此极的方便了编程的处理

  递归解决数字排序问题

  归并排序的中的分冶思想
  

实现代码

def merge_sort(to_sort):
    if not isinstance(to_sort, list):
        return []
    if len(to_sort) == 1:
        return to_sort
    mid = int(len(to_sort) / 2)
    left = merge_sort(to_sort[:mid])
    right = merge_sort(to_sort[mid:])
    result = merge(left, right)
    return result
def merge(left, right):
    if not isinstance(left, list):
        left = []
    if not isinstance(right, list):
        right = []
    result = []
    l_idx = 0
    r_idx = 0
    while l_idx < len(left) and r_idx < len(right):
        if (left[l_idx] < right[r_idx]):
            result.append(left[l_idx])
            l_idx += 1
        else:
            result.append(right[r_idx])
            r_idx += 1
    if l_idx == len(left):
        result.extend(right[r_idx:])
    else:
        result.extend(left[l_idx:])
    return result