算法讲解|分治递归

发表于 更新于 Valine： 本文字数： 2.9k 估计阅读时长 ≈ 3 分钟

什么是递归？

递归和迭代的区别联系

很多人其实都不太清楚递归与迭代的具体差别，迭代指的是你在某一个条件下一直循环 比如

1
for(int i=0;i<100;i++>)

指的就是迭代100次，迭代100次就停止了。

而递归不一样，递归指的是调用自己本身，例如：

1
2
3
4
5
int function1(int n,int m)
{
    n++;m++;
    return function1(n,m);
}

相当于是重复的调用function1这个函数本身。

递归

简而言之就是直接或者间接调用自己的算法，最基本的例子就是函数里调用函数本身就是一种递归调用。 所以每个递归过程都有一个递归函数，递归函数就是用函数自身定义给出定义的函数。

递归算法可以将一个大型的复杂问题转化为一个与原问题相似的规模较小的问题求解，其优势在于用有限的语句定义无限的集合，可以有效减少代码量，使程序简洁易懂；其缺点在于运行效率低，空间消耗大，容易造成堆栈溢出。

但是，需要注意的是，每个递归函数都必须有非递归定义的初始值，以确保递归函数完成计算。

举个例子1

阶乘函数： \[ n!=1(n=0)\\ 或\\ n!=n(n-1)!(n>0) \] 相当于是递归的调用\(n*(n-1)\) 你可能想到了迭代，那我们可以就此写个for循环，但是我们现在讲的是递归，我们写一段Java代码看看他们之间的区别：

递归实现：

1
2
3
4
5
6
7
8
public static int facterial(int n) {
  if (n == 0)
   return 1;
  else if (n < 0)
   return -1;//发生异常，退出
  else
   return n * facterial(n - 1);
 }

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int f(int n) {
  if (n == 0)
   return 1;
  else if (n < 0)
   return -1;//发生异常，退出
  else {
   for (int i = n - 1; i >= 1; i--) {
    n *= i;
   }
   return n;
  }
 
 }

比较算法的好坏我们一般就是用算法的时间复杂度，那我们来比较一下： 针对问题规模为n的问题：

  • 递归实现：时间复杂度O(n)；空间复杂度O(n)。
  • 迭代实现：时间复杂度O(n)；空间复杂度O(1)。

比较可知两种实现的时间复杂度等价，空间复杂度递归占用的略大一下，但是代码的结构清晰度递归更清晰一些。

举个例子2

我们来看一个斐波那契数列的例子 它的递归是这样的： \[ F(n)=1 (n=0,1)\\ 或者\\ F(n)=F(n-1)+F(n-2) (n>1) \]

那我们用代码分别实现一下递归与迭代：

递归实现：

1
2
3
4
5
6
7
8
public static int fibonacci(int n ){
  if(n<0)
   return -1; //发生异常，退出
  else if(n<=1)
   return 1;
  else 
   return fibonacci(n-1)+fibonacci(n-2);
 }

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int F(int n){
  if(n<0)
   return -1; //发生异常，退出
  else if(n<=1)
   return 1;
  else {
   int f0=1,f1=1,fx=0;
   for(int i=2;i<=n;i++){
    fx=f0+f1;
    f0=f1;
    f1=fx;
   }
   return fx;
  }
 }

分析比较一下两种实现方法：

  • 递归实现：时间复杂度O(1.618的n次方)；空间复杂度O(n)。
  • 迭代实现：时间复杂度O(n)；空间复杂度O(1)。

比较可知递归实现的时间复杂度已经非常大了，空间复杂度递归占用的略大一下，但是代码的清晰度递归更清晰一些。

而真正使用起来递归实现的代码是无用代码，用n=40这个数测试一下便知，递归实现的耗时太长了，有兴趣的可以测试一下。

递归优化

那为什么递归看上去这么没用还要介绍呢？

其实递归效率性能较低的原因有以下两点：

  1. 需递归调用工作栈支持（无法避免）

  2. 有可能出现子问题重叠现象（必须尽力避免）

但是递归可以节省代码量，使得程序更明了清楚（其实就是一部分偷懒~）

什么是分治？

字面意思，分而治之

分治策略(又称分治法)是对于一个规模为n的问题，若该问题可以容易地解决则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同。分治策略递归地解这些子问题，再将各个子问题的解合并得到原问题的解。

它的基本步骤，包括了：

分治法的基本步骤：

  1. 分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题；
  2. 解决：若子问题规模较小而容易解决则直接解，否则递归地解；
  3. 合并：将各子问题的解合并为原问题的解。

合并是分治法的关键所在，需要具体问题具体分析。

分治法也不是啥问题都能用 它有适用条件：

  1. 该问题缩小到一定程度可以容易地解决； 该条件对于绝大多数问题能够满足。
  2. 该问题可以分解为若干个规模较小的相同子问题，即问题具有最优子结构性质； 该条件是应用分治法的前提，也是大多数问题可以满足的，反映了递归思想的应用。
  3. 利用该问题分解出的子问题可以合并为该问题的解； 能否利用分治法完全取决于该条件。若具备条件1、2而不具备条件3，可以考虑动态规划法或贪心法。
  4. 该问题的各个子问题是独立的，不包含公共子问题。 该条件涉及分治法的效率。若各子问题不是独立的，则分治法需要很多不必要的工作。

以及，分治策略往往和递归算法同时使用，因此递归算法的时间复杂度分析可适用于分治法。

搞了这么多原理，来讲个例子吧、

例子1

二分查找 给定n个元素组成的有序序列{0:n-1]，在这n个元素中找到特定元素x。若使用顺序查找法，最坏情况下的时间复杂度为O(n)； 利用有序的条件，采用二分查找法可以在最坏情况下将时间复杂度减少到O(log n)。

二分查找法的基本思想是：

将n个元素分成两半，取\(a[n/2]\)与\(x\)比较；

  1. 若\(x = a[n/2]\)，则找到对应元素，查找结束；
  2. 若\(x <a[n/2]\)，则在数组的左半部分继续查找；否则在右半部分继续查找；
  3. 无法再划分时，查找失败；

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int a[],int x,int n)
{
    int low = 0;
    int high = n - 1;
    while(low <= high){
        int middle = (low + high) / 2;//取一半
        if(a[middle] == x)//找到值并且返回
            return middle;
        else if(x < a[middle])//如果比中间数小，就重新定义新的一半上界是中间数左边元素
            high = middle - 1;
        else
            low = middle + 1;//如果比中间数大，就重新定义新的一半下界是中间数右边元素
    }
    return -1;
}