递归

什么是递归？如果为了描述问题的某一状态，需要用到它的上一状态；而描述上一状态，又必须用到它的再上一状态……这样用自已来定义自己的方法称为递归。

数学表达式：f(n) = n*f(n－1) (n>0)

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

递归的两个要素

递归的边界条件

边界条件是需要解决的问题的最简单的情况，比如，当n=0或n=1时，f(n)=1 —— 直接可以得到问题的答案，不需要使用f(n-1)进行递归。同时，边界条件是递归停止的条件，如果没有边界条件，或没有进行合理设置边界条件，递归会进入死循环。

递归的定义

递归定义是使问题向边界条件转化的规则。在设计递归定义的时候，必须能使问题越来越简单，比如，如果f(n)可以由f(n-1)来定义，那么不断地递归，整个方法会越来越靠近f(0)或f(1)的递归边界，从而获得最终的结果。

递归的适用条件

1. 数据的定义形式按递归定义，比如，裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2。
2. 数据之间的关系（即数据结构）按递归定义，比如，树的遍历, 图的搜索等。
3. 问题解法按递归算法实现，比如，回溯法等。

优缺点

优点

结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点

递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

缺点的解决方法

在递归算法中消除递归调用，使其转化为非递归算法。

1. 采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。
2. 用递推来实现递归函数。
3. 通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善，但其适用范围有限。

递归算法实例（Python 3）

计算数的阶乘

def factorial(n: int) -> int:
    """
    当n>=0时，对n进行阶乘计算。
    阶乘函数可以定义为：
    n! = | 1               n = 0
         | n * (n-1)!      n > 0
         | -1              n < 0
    :param n:
    :return:
    """
    if n < 0:
        return -1
    else:
        if n == 0:
            return 1  # 边界条件
        else:
            return n * factorial(n - 1)  # 递归方程

计算斐波那契数列的第n个数

def fibonacci(n: int) -> int:
    """
    当n>=0时，无穷数列1,1,2,3,5,8,13,21,34,55,...，称为Fibonacci数列。
    Fibonacci数列的第n个数可以定义为：
    f(n) = | 1                 n = 0
           | 1                 n = 1
           | f(n-1) + f(n-2)   n > 0
           | -1                n < 0
    :param n:
    :return:
    """
    if n < 0:
        return -1
    else:
        if n == 0:
            return 1  # 边界条件
        elif n == 1:
            return 1  # 边界条件
        else:
            return fibonacci(n-1) + fibonacci(n-2)  # 递归方程

计算正整数n划分成一系列正整数之和的种类数量

def partition(n: int) -> list:
    """
    整数划分问题
    将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。
    正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。
    如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。
    q(n,m) = | 1                     m,n = 0
             | q(n,n)                n < m
             | 1 + q(n,n-1)          n = m
             | q(n,m-1) + q(n,m)     n > m > 1
    正整数n的划分数p(n)=q(n,n)
    例如，正整数6有如下11种不同的划分：
    6；
    5+1；
    4+2，4+1+1；
    3+3，3+2+1，3+1+1+1；
    2+2+2，2+2+1+1，2+1+1+1+1；
    1+1+1+1+1+1
    :param n:
    :return: 返回多少种划分种类
    """
    return partition_1(n,n)


def partition_1(n: int,m: int) -> list:
    """
    整数划分问题
    将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。
    正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。
    如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。
    q(n,m) = | 1                     m,n = 0
             | q(n,n)                n < m
             | 1 + q(n,n-1)          n = m
             | q(n,m-1) + q(n,m)     n > m > 1
    正整数n的划分数p(n)=q(n,n)
    例如，正整数6有如下11种不同的划分：
    6；
    5+1；
    4+2，4+1+1；
    3+3，3+2+1，3+1+1+1；
    2+2+2，2+2+1+1，2+1+1+1+1；
    1+1+1+1+1+1
    :param n:
    :param m: 最大划分数字不超过m的划分数
    :return: 返回多少种划分种类
    """
    if n <= 0:
        return -1
    else:
        if n == 1 or m == 1:
            return 1  # 边界条件
        elif n < m:
            return partition_1(n, n)  # 递归方程
        elif n == m:
            return 1 + partition_1(n, n-1)  # 递归方程
        else:
            return partition_1(n, m-1) + partition_1(n-m, m)  # 递归方程

分治

分治就是分而治之，就是把一个大问题分成多个相同或相似的子问题，再把子问题分成更小的子问题……直到最后的子问题可以直接求解出来，然后将所有子问题的解的合并，就得到了大问题的解。

分治和递归的区别是什么？

分治是一种思想，并不涉及到具体的算法。在大多数情况下，分治的思想需要借助递归算法来实现。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

简单的说：分治法就是把1个分为多个,递归法就是把多个归一的解决问题方法。