数据结构与算法之递归 + 分治

数据结构与算法之递归 + 分治-五分钟学算法

01.
递归

每谈到递归，我们总会免不了联系到斐波那契(Fibonacci)数列，当然也不可忽视，斐波那契数列确实是一个很好的例子。但在现实当中，我们只有在迫不得已的情况下才使用递归，因为递归本身的效率并不理想，但他的思想却值得我们留存在记忆之中。

题目一：写一个函数，输入n，求斐波那契数列的第n项。

我们先一起看一下该题目的递归实现，从而学会写递归的三要素：

//第一要素：明确你这个函数想要干什么
//函数功能：计算斐波那契数列的第n项
long long Fibonacci(unsigned int n)
{
//第二要素：寻找递归结束条件
if( n <= 1)
return i == 0 ? 0 : 1;
//第三要素：找出函数的等价关系式
return Fibonacci(n – 1) + Fibonacci(n – 2);
}

但在面试的时候，面试官可不会轻易放过你，他会觉着上面的递归实现效率太低，原因在于我们在求斐波那契数列第n项的时候，中间计算了很多重复项，而且是不必要的计算，如下图的递归树：

改进的方法并不复杂，那就是直接使用迭代的方式进行处理，避免重复计算就可以了。

long long Fibonacci(unsigned int n)
{
int result[2] = {0,1};
if(n < 2)
return result[n];

long long fibNumOne = 1;
long long fibNumTwo = 0;
long long fibN = 0;
for(int i = 2; i <= n; i++){
fibN = fibNumOne + fibNumTwo;

fibNumTwo = fibNumOne;
fibNumOne = fibN;
}

return fibN;
}

在高级语言中，函数自己调用和调用其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。

不过，写递归程序最怕的就是陷入永不结束的无穷递归中。切记，每个递归定义必须至少有一个终止条件，当满足这个条件时递归不再进行，即函数不再调用自身而是返回值。

对比了上面所提到的两种实现斐波那契的代码，迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。

使用递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。

但大量的递归调用会建立函数的副本，会消耗大量的时间和内存，而迭代则不需要此种代价。

递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序。

今日主要介绍递归，关于迭代只是简要提及，防止大家面试时避免失误。后面几个例子都是关于递归实现。

题目二：写一个函数，输入n，求n的阶乘n!。

//第一要素：明确你这个函数想要干什么
//函数功能：计算n的阶乘
long long f(unsigned int n)
{
//第二要素：寻找递归结束条件
if( n <= 2)
return n;
//第三要素：找出函数的等价关系式
return n * f(n – 1);
}

题目三：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

//第一要素：明确你这个函数想要干什么
//函数功能：计算青蛙跳上一个n级的台阶总共有多少种跳法
long long jump(unsigned int n)
{
    //第二要素：寻找递归结束条件
    if( n <= 2)
        return n;
    //第三要素：找出函数的等价关系式
    return jump(n - 1) + jump(n - 2);
}

一定要注意递归结束条件是否够严谨问题，有很多人在使用递归的时候，由于结束条件不够严谨，导致出现死循环。所以，当我们在第二步找出了一个递归结束条件的时候，可以把结束条件写进代码，然后进行第三步，但是请注意，当我们第三步找出等价函数之后，还得再返回去第二步，根据第三步函数的调用关系，判断会不会出现一些漏掉的结束条件，并进行查漏补缺。

题目四：编写一个递归函数，实现将输入的任意长度的字符串反向输出的功能。

要将一个字符串反向地输出，小禹禹们一般采用的方法是将该字符串存放到一个数组中，然后将数组元素反向的输出即可。这道题要求输入是任意长度，所以使用递归会比较容易解决。

我们说过，递归三要素的第二要素是需要有一个结束的条件，那么我们可将“#”作为一个输入结束的条件。

//第一要素：明确你这个函数想要干什么
//函数功能：将输入的任意长度的字符串反向输出
void print()
{
    char a;
    scanf("%c", &a);

    //第三要素：找出函数的等价关系式
    if( a != '#') print();
    //第二要素：寻找递归结束条件，#表示递归结束，进行返回输出。
    if( a != '#') printf( "%c", a);
}

假设我们从屏幕上输入字符串：ABCDE#

02.
分治思想

分而治之的思想古已有之，秦灭六国，统一天下正是采取各个击破、分而治之的原则。

而分治思想在算法设计中也是非常常见的，当一个问题规模较大且不易求解的时候，就可以考虑将问题分成几个小的模块，逐一解决（这种思想在以后的工作更是深有体会，处世之道）。

分治思想和递归就像是亲兄弟的关系，因为采用分治思想处理问题，其各个小模块通常具有与大问题相同的结构，这种特性也使递归技术有了用武之地。我们接下来以折半查找来讲解分治思想。

折半查找法是一种常用的查找方法，该方法通过不断缩小一半的查找范围，直到达到目的，所以效率比较高。

线性检索和二分检索求 1 的位置：

线性检索和二分检索求 23 的位置：

背景：一位法国数学家曾编写过一个印度的古老传说：在世界中心贝纳勒斯的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。

僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

这其实也是一个经典的递归问题。我们可以做这样的考虑：

• 先将前63个盘子移动到Y上，确保大盘在小盘下。

• 再将最底下的第64个盘子移动到Z上。

• 最后将Y上的63个盘子移动到Z上。

接下来，我们要做的就是将Y上的前62个盘子借助Z移动到X上，再将最底下的第63个盘子移动到Z上，后面就是重复这一操作，直到剩一个盘子是，直接将该盘子由X移动到Z。

景禹给你说了，可能还是有点点朦胧，没关系，回头你在玩一玩这个游戏，你就知道如何操作了。给大家分享的《数据结构与算法》第三十三讲递归和分治思想3中有这个有游戏。

题目五：编程实现汉诺塔的移动过程。

#include <stdio.h>
//第一要素：明确你这个函数想要干什么
// 函数功能：将 n 个盘子从 x 借助 y 移动到 z
void move(int n, char x, char y, char z)
{
    //第二要素：寻找递归结束条件，当n=1时，直接将盘子从x移动到z
  if( 1 == n )
  {
    printf("%c-->%cn", x, z);
  }
  else
  {
        //第三要素：找出函数的等价关系式，并不考虑具体的移动过程，仅考虑完成任务
    move(n-1, x, z, y); // 将 n-1 个盘子从x借助z移到y上
    printf("%c-->%cn", x, z);// 将第n个盘子从x移到z上
    move(n-1, y, x, z); // 将 n-1 个盘子从y借助x移到z上
  }
}

int main()
{
  int n;

  printf("请输入汉诺塔的层数: ");
  scanf("%d", &n);
  printf("移动的步骤如下: n");
  move(n, 'X', 'Y', 'Z');

  return 0;
}

END

作者：景禹，一个追求极致的共享主义者，想带你一起拥有更美好的生活，化作你的一把伞。