大家好，欢迎来到IT知识分享网。

从数学归纳法到递归算法

数学归纳法（Mathematical Induction, MI）

• 简介

  常用的数学证明方法，属于完全严谨演绎推理方法，常被用于证明给定命题在给定定义域范围内成立，而广义的数学归纳法也可用于证明一般的良基关系，如集合论中的树，广义数学归纳法在数学逻辑和计算机科学领域被称为结构归纳法

• 思维步骤

  • 证明

    任意给定情形都是正确的

  • 核心要点

    需要弄到两个条件即可证明

    1. 知道第一个元素是满足要求的
    2. 知道前一个元素满足要求和后一个元素满足要求之间具有某种固定联系。这样就可以通过一个一个的递推证明出所有元素是满足要求的

  • 分析过程

    • 第一步

      通常证明 N = 1 时成立，并把 N = 1 带入关系式，得出 N = 1 满足关系式

    • 第二步

      证明 N > 1 时，假设 N – 1 时该关系式成立可以进一步成功推出 N 时该关系式也是成立的

• 总结

  想要求出一系列的数据满足某种条件，这一系列的数据又满足某种环环相扣的联系，那么你只需要知道锁链的一端，也就是第一个元素，你还需要知道环环之间是如何相扣的，也就是环环之间的联系，就可得到锁链中的每一个环节，这就是数学归纳法的基本思想

• 模型

  已知 n = 1 满足关系式，n > 2 时，通过 n – 1 满足关系式推出 n 满足关系式，即可证明

• 例题

  请尝试用数学归纳法证明：n∈N* 时，1/(1×3) + 1/(3×5) + 1/(2n-1)(2n+1) = n/(2n+1)

递推算法（Recursion method, RM）

• 简介

  递推是一个数学上的概念，如数列中常见的递推式，a[n] = a[n-1] + a[n-2]，数学上的递推函数在计算机中可以通过递归来实现，也可以不通过递推来实现

• 思维步骤

  • 求解

    有三个或更多个元素之间有某种关系（如 a[n]，a[n - 1]，a[n - 2]），已知初始值，求 n 为某个值时候 a[n] 的值

  • 核心要点

    需要两种思路，两种思路都可以用程序来解决

    1. 抓住循环，层层往上求解（递推）
    2. 抓住关系式和初始条件（递归）

• 总结

  递推算法抓住循环要点，一层层往上计算数值即可，虽然代码量较多，也不如递归来的精巧，但时间复杂度却比递归要少

• 模型

  已知至少两个初始值，层层网上推演，计算较大值

• 例题

  请尝试用递归和非递归的方法求解 n 等于某一值时 a[n] 的值（斐波那契数列）

  • 递归实现

    int function(int n){ 
           
        if(n<=2)
            return 1;
        return function(n - 1) + function(n - 2);
    }
    

    这里是计算机中的函数 function(n) 但是却很类似于数学中的式子 a[n]，return 相当于等于什么，也就是 function(n) = function (n - 1) + function(n - 2)，当然这是需要 n > 2 时，也就类似于数学式 a[n] = a[n - 1] + a[n - 2]，计算机中会不断循环调用自己，最后有个出口 n <= 2 时，程序弹出并层层向上返回。但计算机这里用到了循环，n = 3 计算了 3 次，n = 4 计算了 5 次，n = 5 计算了 9 次，n = 6 计算了 15 次，n = 7 计算了 25 次…后一个次数是前两个次数之和 + 1。这里不做时间复杂度计算分析，以后的博文中会介绍时间复杂度以及空间复杂度利用计算机理论和数学知识来进行分析和计算。用数据结构中的知识是其时间复杂度是 n – 1 不完全二叉树的节点数，所以近似是 O(2^n)，用数学方法计算，可以将其转化为二阶常系数齐次差分方程，最后可以解出约等于 O(1.618^n)，即指数级复杂度O(2^n)，这里也不做详细讲解，学过些高等数学的都需要会解

  • 非递归实现

    int function(int n){ 
           
    	int f1 = 1, f2 = 1;
        if(n <= 2)
            return 1;
        for(int i = 3; i <= n; i++){ 
           
            int f = f1 + f2;
            f1 = f2;
            f2 = f;
        }
        return f;
    }
    

    实际上就是抓住了循环二字，进而求出 a[n]，其时间复杂度为 O(n)

递归算法（Recursive algorithm, RA）

• 简介

  计算机科学中指将重复问题分解为同类的子问题来进行解决的方法，目前绝大部分编程语言都是支持函数自调用，递归方法实际上就是一个没有 for 和 while 的循环

• 思维步骤

  见上面的递推算法中的思维步骤

  另外再说一个递归算法的核心要点：如果把递推看成层层往上叠，进行循环求解，那么递归可以直接看成一个树形结构，利用数据结构的知识即可求解递归算法中需要了解的东西

• 总结

  递归比较像倒着推理的递推或者说倒着推理的数学归纳法，但最后求解依然是需要两个基本要素：1.初始值 2.关系式。递归方法可以想象成一个树形结构图，那么求解递归方法的时间复杂度也很容易求了，就是树的节点数 O(2^n)的，递推算法可以想象成层层往上叠，不断循环求解元素的模型。递推和递归实际上是同一个问题的两种思维方式罢了，都是为了解决同一个问题

• 模型

  把规模较大的难题转化为多个新的较简单的问题，而这些问题的解决方式仍与原问题一样，只是处理对象不同，就这样问题越分越多，但是问题的难度也越来越小，直到找到“出口”——初始值

• 例题

  见上面递推算法中的例题

由数学归纳法到递归算法

• 总结

  站在一个更高的高度来看待这些问题，其实依旧逃不开两个要素：1.初始值 2.关系式。

  数学归纳法是正向推理，一条锁链从头到尾，递归是逆向推理，一条锁链从尾到头，到达端点后再依次从头到尾，最后解决问题。

  数学归纳法是已知一个值满足条件（锁链的头端）（初始值），当知道 n – 1 满足条件和 n 满足条件之间具有某种关系后（锁链环与环之间是如何连接的）（关系式），即可证明关系式成立

  递归是已知多个初始值（锁链的头端）（初始值），当知道 a[n]，a[n + 1]，a[n + 2] 之间具有某种关系后（锁链环与环之间是如何连接的）（关系式），即可求解较大值

  数学归纳法是一个值，递归多个值，数学归纳法是值满足条件，递归是值等于什么，数学归纳法是值满足条件和值满足条件之间的关系，递归是值与值之间的关系，数学归纳法是证明关系式，递归是求解 n，当把值满足条件看成值等于多少（值等于多少从本质来看就是值满足一个什么条件），这样来说数学归纳法和递归算法从本质来讲就是一个东西