递归是什么

递归，其实就是指函数调用自身的行为，比较简单也比较好理解。类似于我们中学的时候学数列的时候用的递推公式。就拿两个经典的例子来说说。

阶乘

我们中学的时候学的阶乘的定义是什么呢？大概是写成这样：

n!=n\cdot(n-1)\cdot(n-2)\cdot(n-3)\ldots2\cdot1

其实简单一点写也可以这样：

n!=\prod_{i=1}^ni

可以看到，每一个乘数都会减一，直到最后为1了为止。那么我们其实可以理解为：

n!=n\cdot(n-1)!\quad (当然，减到1的时候就停止)

这样，随着后面的阶乘一层一层解包，最后就能够达到一个完整的阶乘式子。因此我们可以这么理解：一个数如果大于1，那么就乘以它-1的阶乘，如果等于1则停止。这样一来，你会发现如果还没有减到1的时候，就会调用一个新的阶乘。在阶乘中调用阶乘，符合递归的定义。

代码演示：

// Java
public int Fac(int n)
{
    if (n < 0) 
    {
        return -1;//条件不合法
    }
    else if (n == 0 || n == 1)
    {
        return 1;//递归结束的限定条件
    }
    else
    {
        return n*Fac(n - 1);
    }
}

// C/C++
int Fac(int n)
{
    if (n < 0)
    {
        return -1;//条件不合法
    }
    else if (n == 0 || n == 1)
    {
        return 1;//递归结束条件
    }
    else
    {
        return n*Fac(n - 1);
    }
}

# Python
import sys
sys.setrecursionlimit(100000) #括号中的值为最大递归深度
#如果递归调用的深度超过了Python默认的深度，那么就会报错，加上上面的语句就可以人为改动最大递归深度
def Fac(n:int) -> int:
    if n < 0:
        return -1 #条件不合法
    elif n == 0 or n == 1:
        return 1 #递归结束条件
    else:
        return n*Fac(n - 1)

// Go
func Fac(n uint64) uint64
{
    if (n < 0)
    {
        return -1 //条件不合法
    }
    else if (n == 0 || n == 1)
    {
        return 1 //递归结束条件
    }
    else
    {
        return n*Fac(n - 1)
    }
}

斐波那契数列

比起阶乘，斐波那契数列就更能够说明递归的思路。上面的阶乘我们还可以通过循环来解决，但是斐波那契数列使用递归的方式来生成，比其他任何一种方式都容易理解。我们知道，斐波那契数列就是将前两项加起来作为当前项，第一项始终为1。

那么我们就可以写出以下思路：

判断输入的项数，1 或 2 则输出 1
大于 2，则输出前两项之和

写成代码就是：

// Java
public int Fibo(int n)
{
    if (n < 0)
    {
        return -1;//条件不合法
    }
    else if (n <= 2)
    {
        return 1;//递归终止条件
    }
    else
    {
        return Fibo(n - 2) + Fibo(n - 1);
    }
}

// C/C++
int Fibo(int n)
{
    if (n < 0)
    {
        return -1;//条件不合法
    }
    else if (n <= 2)
    {
        return 1;
    }
    else
    {
        return Fibo(n - 2) + Fibo (n - 1)
    }
}

# Python
def Fibo(n:int) -> int:
    if n < 0:
        return -1 #条件不合法
    elif n <= 2:
        return 1 #递归结束条件
    else:
        return Fibo(n - 2) + Fibo(n - 1)

// Go
func Fibo(n int) int
{
    if (n < 0)
    {
        return -1 //条件不合法
    }
    else if (n <= 2)
    {
        return 1 //递归终止条件
    }
    return Fibo(n - 2) + Fibo(n - 1)
}

所谓分治

分治法其实我觉得就一句话：大事化小，小事化了。对于一个解决起来很复杂的问题，我们可以按照一定的规则，把问题分解成小问题，这样就能够很快解决。

不能理解？其实我们常用的二分法就是一个很典型的分治法。

在一个有序的数列里面，要寻找一个数，不需要挨个比对，先把数列平均分成两部分，然后检查一下我们要寻找的数和分界点的大小关系，然后确定所在区间，对这个区间采用刚刚同样的办法去处理。这样很快就可以找到一个数。

比如这里有个 1 到 100 的序列，我要找 80，那么就开始比。80 显然比 50 大，那么就在 $[51,100]$ 里面找。80 显然比 75 大，那么范围进一步缩小到 $[76,100]$ 。继续，80 比 87 小，范围缩减到 $[76,87]$ 。80 比 81 小，范围缩减至 $[76,81]$ 。80 比 78 大，范围缩减至 $[79,81]$ 。80 和 80 相等，于是我们找到了 80 这个数。总共比较了 6 次就找到了，比挨个比较快多了。

快速排序初步

如果你能够理解上面两种思维，那么快速排序对于你来说，就很简单了。

快速排序，简单来说，就是先在序列里面选择一个基准值（选哪一个都可以），然后把比基准值大的数放在基准值的右边，把比基准值小的数放在基准值左边，然后再分别对左右两部分执行刚才的操作，直到不能再分了为止。这样出来就是一个从小到大排序的序列了。

比如：

[3,1,2,5,4]

这里为了方便，我们选择第一个数 3 作为基准值，排序一遍：

[1,2]\ [3]\ [5,4]

左边的子序列选择第一个数作为基准值，排序第二遍：

[1]\ [2]\quad[3]\ [5,4]

左边子序列排序完成，开始排序右边，选择第一个数作为基准值，排序第三遍：

[1]\ [2]\quad[3]\quad[4]\ [5]

右边子序列排序完成，原始序列排序完成：

[1,2,3,4,5]

挺简单的吧。我们只需要设计一遍思路，剩下的让它去递归就行了。

说到递归，知道递归的只有 3 种人：

讨厌递归的
喜欢递归的
一开始讨厌，后来变得喜欢的

笔者就是第三种人。其实递归只要get到了它的精髓，一点都不难，反而还会觉得很直观。当然凡事都无绝对，在不适合用递归的时候强行用递归，那估计很难有人能够理解你的代码了。正所谓“普通程序员用迭代，天才程序员用递归”，大概说的就是这个道理。合适的才是最好的。

快排的基准值选取

当然，快速排序也是有很多门道在里面的。比如基准值的选取，这就会直接决定你的快速排序的运行时间。

我们刚刚在例子中，都是以第一个数作为基准值，这其实是不太恰当的，只不过我恰好举了个比较好的例子。

不信？看这个：

[5,4,3,2,1]

要求从小到大排序。

如果你还用第一个值作为基准值，那就傻眼了：因为这样就会导致每次的左边子序列都是一个空序列，这样，快速排序就被你硬生生地用成了瘸子，非常慢。

我们知道，这个序列显然用 3 做基准值是比较好的，但是计算机不知道。那么我们来想点别的办法。

随机法

我们可以直接用一个随机位置的值来作为基准值，这样就比刚刚要安全一些。如果你调用的随机函数是正常的，那么生成的值一般不会太奇怪，至少比刚刚那个方案靠谱多了。但是偶尔还是会存在一些不稳定的情况。

三数中值法

我们知道，最佳的基准值应该是这个序列的中值，所谓中值，就是一个有序数列的中间值。那么原理上只有有序数列才能够求出中值。那我都有序了还要排序干嘛？

因此，我们只能通过一些方法来近似逼近中值，来寻求我们力所能及的最佳基准值。

我们可以沿用随机法的思路，随机出几个值，然后再选取它们的中值，作为整个数列排序的基准值。但是这个方法也要看着用，毕竟选取数值太多了会影响效率，太少了又会影响精度。因此人们一般随机出 3 个值，以它们的中值来作为整个排序的基准值。

但是我们知道，一个乱序的序列，其实我们本身就可以认为它是随机的，因为我们采集的数据大多都是毫无规律，你无法通过这一组数据来推测出下一组会是个什么样的序列。因此，我们随机函数也可以省去，直接用这个乱序序列的首尾和中间的数值这三个来作为基准值的参考即可。

至于代码，我将会在《快速排序：进阶》中详细讲解，敬请期待。

递归与分治