什么是递归

递归的定义

在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数p调用过程或函数q，而q又调用p，称之为间接递归。 任何间接递归都可以等价地转换为直接递归。 　 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。

【例2.1】设计求n!（n为正整数）的递归算法。

int fun(int n)
{  if (n==1)			//语句1
　　　return(1);		//语句2
　 else				//语句3
　　　return(fun(n-1)*n);	//语句4
}

直接调用fun(n-1)，所以一个直接递归函数。且是最后一条语句，所以又属于尾递归。

能够用递归解决的问题应该满足以下三个条件：

• 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。
• 递归调用的次数必须是有限的。
• 必须有结束递归的条件来终止递归。

何时使用递归

在以下三种情况下，常常要用到递归的方法。

定义是递归的

​ 有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci数列等。可以将其递归定义直接转化为对应的递归算法。

数据结构是递归的

​ 有些数据结构是递归的。例如单链表，其结点类型声明如下：

typedef struct LNode 
{   ElemType data;
    struct LNode *next;	  
} LinkList;      

​ 结构体LNode的定义中，指针域next是一种指向自身类型的指针，所以它是一种递归数据结构。

• 不带头结点单链表示意图

• 如果带有头结点又会怎样呢？？？

  对于递归数据结构，采用递归的方法编写算法既方便又有效。例如，求一个不带头结点的单链表L的所有data域（假设为int型）之和的递归算法如下：

  int Sum(LinkList *L)
  {   if (L==NULL)
  　　　　return 0;
  　　else 
  　　　　return(L->data+Sum(L->next));
  } 

【例2.2】分析二叉树的二叉链存储结构的递归性，设计求非空二叉链bt中所有结点值之和的递归算法，假设二叉链的data域为int型。

解：二叉树采用二叉链存储结构，其结点类型定义如下：

typedef struct BNode
{   int data;
    struct BNode *lchild，*rchild;
} BTNode;		//二叉链结点类型

int Sumbt(BTNode *bt)		//求二叉树bt中所有结点值之和
{  if (bt->lchild==NULL && bt->rchild==NULL)
      return bt->data;	//只有一个结点时返回该结点值
   else				//否则返回左、右子树结点值之和加上根结点值
      return Sumbt(bt->lchild)+ Sumbt(bt->rchild)+bt->data);
}

问题的求解方法是递归的

典型的有Hanoi问题求解。

规则：每次只能移动一个盘片；盘片可以插在X、Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。

设Hanoi(n，x，y，z)表示将n个盘片从x通过y移动到z上，递归分解的过程是：

​

flowchart TB

a1["Hanoi(n，x，y，z)"]
a2["Hanoi(n-1，x，z，y)"]
a3["move(n，x，z):将第n个圆盘从x移到z；"]
a4["Hanoi(n-1，y，x，z)"]
a5["“大问题”转化为若干个“小问题”求解"]
    subgraph y
    a2 -.-
    a3 -.-
    a4 
    
    end
    subgraph x
    a1
    end
    
    a5-.->a1
    a5-.->a2
    a5-.->a4
    x ==> y

递归模型

递归模型是递归算法的抽象，它反映一个递归问题的递归结构。例题2.1求n!的递归算法对应的递归模型：

(1)式给出递归的终止条件，(2)式给出fun(n)的值与fun(n-1)的值之间的关系， (1)式称为递归出口， (2)式称为递归体。

​ 一个递归模型是由递归出口和递归体两部分组成。

• 递归出口的一般格式如下：

  $$f(s1)=m1$$

• s1与m1均为常量，有些递归问题可能有几个递归出口。

• 递归体的一般格式如下：

  $$f(s_{n+1})=g(f(s_i)，f(s_{i+1})，…，f(s_n)，c_j，c_{j+1}，…，c_m)$$

  $s_{n+1}$是一个递归“大问题”，$s_i、s_{i+1}、…、s_n$为递归“小问题”，$c_j、c_{j+1}、…、c_m$是若干个可以直接（用非递归）解决的问题，g是一个非递归函数，可以直接求值。

递归算法的执行过程

• 递归程序虽然每次调用的是相同的子程序，但它的参量、输入数据等均有变化。
• 随着调用的不断深入，必定会出现调用到某一层的函数时，不再执行递归调用而终止函数的执行，即遇到递归出口。
• 递归调用是函数嵌套调用的一种特殊情况，即它是调用自身代码。
• 由于每次调用时，它的参量和局部变量均不相同，因而也就保证了各个复制件执行时的独立性。
• 系统为每一次调用开辟一组存储单元，用来存放本次调用的返回地址以及被中断的函数的参量值。
• 这些单元以系统栈的形式存放，每调用一次进栈一次，当返回时出栈，把当前栈顶保留的值送回相应的参量中进行恢复，并按栈顶中的返回地址，从断点继续执行。

例2.1，求5!即执行fun(5)时内部栈的变化及求解过程如下：

• 由以上内容可得出
  • 每递归调用一次，就需进栈一次，最多的进栈元素个数称为递归深度，当n越大，递归深度越深，开辟的栈空间也越大。
  • 每当遇到递归出口或完成本次执行时，需退栈一次，并恢复参量值，当全部执行完毕时，栈应为空。
  • 递归调用分两步：第一步是分解过程，即用递归体将“大问题”分解成“小问题”，直到递归出口为止，然后进行第二步的求值过程，即已知“小问题”，计算“大问题”。前面的fun(5)求解过程如下所示。

【例2.3】 Fibonacci数列定义为：

【例2.3】 Fibonacci数列定义为：
Fib(n)=1			n=1
Fib(n)=1			n=2
Fib(n)=Fib(n-1)+Fib(n-2)	n>2
对应的递归算法如下：
int Fib(int n)
{　 if (n==1 || n==2)
　　　　return 1;
　　else
    return Fib(n-1)+Fib(n-2);
}
画出求Fib(5)的递归树以及递归工作栈的变化和求解过程。

• 解：求Fib(5)的递归树如下：

从上面的过程看到，对于复杂的递归调用，分解和求值可能交替进行、循环反复，直到求出最终值。

执行Fib(5)时递归工作栈的变化和求解过程：

• 在递归函数执行时，形参会随着递归调用发生变化，但每次调用后会恢复为调用前的形参，将递归函数的非引用型形参的取值称为状态。

• 递归函数的引用型形参在执行后会回传给实参，有时类似全局变量，不作为状态的一部分。

  • 例如，有以下递归程序：

    #include <stdio.h>
    void f(int n)
    {　 if (n<1) return;
    　　   else
    　　{	printf("调用f(%d)前，n=%d\n"，n-1，n);
        f(n-1);
        printf("调用f(%d)后:n=%d\n"，n-1，n);
    　　}
    }
    

    执行f(4)的结果

    调用f(3)前，n=4 调用f(2)前，n=3 调用f(1)前，n=2 调用f(0)前，n=1 调用f(0)后: n=1 调用f(1)后: n=2 调用f(2)后: n=3 调用f(3)后: n=4

  • 在上述递归函数f中，状态为（n），其递归执行过程如图，输出框旁的数字表示输出顺序，虚线表示本次递归调用执行完后返回，从中看到每次递归调用后状态都恢复为调用前的状态。

递归算法设计

递归与数学归纳法

• 第一数学归纳法原理：若{P(1)，P(2)，P(3)，P(4)，…}是命题序列且满足以下两个性质，则所有命题均为真： （1）P(1)为真。 （2）任何命题均可以从它的前一个命题推导得出。

  $$\begin{aligned} &例如，采用第一数学归纳法证明下式：\\ &1+2+…+n=\frac{n(n+1)}{2}\\ &证明：当n=1时，左式=1，右式=\frac{1×2}{2}=1，左右两式相等，等式成立。\\ &　　假设当n=k-1时等式成立，有1+2+…+(k-1)= \frac{k(k-1)}{2}\\ &　　当n=k时，左式=1+2+…+k=1+2+…+(k-1)+k=\frac{k(k-1)}{2}+k=　\frac{k(k+1)}{2}\\ &等式成立。即证。 \end{aligned}$$

• 第二数学归纳法原理：若{P(1)，P(2)，P(3)，P(4)，…}是满足以下两个性质的命题序列，则对于其他自然数，该命题序列均为真： （1）P(1)为真。 （2）任何命题均可以从它的前面所有命题推导得出。 归纳步骤（条件2）的意思是P(n)可以从前面所有命题假设{P(1)，P(2)，P(3)，…，P(n-1)}推导得出。

  $$\begin{aligned} &　　例如，采用第二数学归纳法证明，任何含有n（n≥0）个不同结点的二叉树，都可由它的中序序列和先序序列唯一地确定。\\ &证明：当n=0时，二叉树为空，结论正确。\\ &　　假设结点数小于n的任何二叉树（所有结点值不相同），都可以由其先序序列和中序序列唯一地确定。\\ & 若某棵二叉树具有n个不同结点，其先序序列是a_0 a_1 … a_k a_{k+1} … a_{n-1}、中序序列是b_0 b_1 … b_{k-1} b_k b_{k+1} … b_{n-1}\\ \end{aligned}$$

  　　 根据归纳假设，由于子先序序列$a_1…a_k和子中序序列b_0b_1…b_{k-1}$可以唯一确定根结点a0的左子树，而子先序序列$a_{k+1}…a_{n-1}和子中序序列b_{k+1}…b_{n-1}$可以唯一地确定根结点$a_0$的右子树。 　　综上所述，这棵二叉树的根结点己经确定，且其左、右子树都唯一确定，所以整个二叉树也就唯一地确定。

  数学归纳法是一种论证方法，而递归是算法和程序设计的一种实现技术，数学归纳法是递归的基础。

  递归算法设计的一般步骤

  递归算法设计先要给出递归模型，再转换成对应的C/C++语言函数。

  获取递归模型的步骤：

  $$\begin{aligned} &（1）对原问题f(s_n)进行分析，抽象出合理的“小问题”f(s_{n-1})（与数学归纳法中假设n=k-1时等式成立相似）；\\ &（2）假设f(s_{n-1})是可解的，在此基础上确定f(s_n)的解，即给出f(s_n)与f(s_{n-1})之间的关系（与数学归纳法中求证n=k时等式成立的过程相似）；\\ &（3）确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口（与数学归纳法中求证n=1或n=0时等式成立相似）。\\ \end{aligned}$$

  【例2.5】用递归法求一个整数数组a的最大元素。

  $$\begin{aligned} &　　解：设f(a，i)求解数组a中前i个元素即a[0..i-1]中的最大元素，则f(a，i-1)求解数组a中前i-1个元素即a[0..i-2]中的最大元素，\\&前者为“大问题”，后者为“小问题”。\\ &　　假设f(a，i-1)已求出，则有f(a，i)=MAX\{f(a，i-1)，a[i-1]\}。\\&递推方向是朝a中元素减少的方向推进，当a中只有一个元素时，该元素就是最大元素，所以f(a，1)=a[0]。 \\ \end{aligned}$$

  由此得到递归模型如下：

  f(a，i)=a[0]					当i=1时
  f(a，i)=MAX{f(a，i-1)，a[i-1]}		当i>1时
  

  对应的递归算法如下：

  #include <stdio.h>
  #define max(a,b) ((a>b)?a:b)
  int fmax(int a[],int i)
  {      if (i==1)
        return a[0];
      else
       return max(fmax(a,i-1),a[i-1]);
  }
  int main()
  {
      int a[]={21,9,3,6,5};
      printf("fmax=%d\n",fmax(a,5));
      return 0;
  }
  

  递归数据结构及其递归算法设计

  递归数据结构的定义

  ​ 采用递归方式定义的数据结构称为递归数据结构。在递归数据结构定义中包含的递归运算称为基本递归运算。

  $$\begin{aligned} &递归数据结构定义：\\ &RD=(D，Op)\\ &其中，D={di}（1≤i≤n）为所有元素的集合。\\ &Op是基本递归运算的集合，Op=\{op_j\}（1≤j≤m），对于\forall d_i∈D，\\&不妨设op_j为一元运算符，则有op_j(d_i)∈D，也就是说，递归运算符具有封闭性。\\ \\ &二叉树的定义中，D是给定二叉树及其子树的集合（对于一棵给定的二叉树，其子树的个数是有限的），\\ &Op={op_1，op_2}由基本递归运算符构成，它们的定义如下：\\ &op_1(p) = p->lchild\\ &op_2(p) = p->rchild\\ &其中，p指向二叉树中的一个非空结点。\\ \end{aligned}$$

  基于递归数据结构的递归算法设计

  单链表的递归算法设计

  在设计不带头结点的单链表的递归算法时： 设求解以L为首结点指针的整个单链表的某功能为“大问题”。 而求解除首结点外余下结点构成的单链表（由L->next标识，而该运算为递归运算）的相同功能为“小问题”。 由大小问题之间的解关系得到递归体。 再考虑特殊情况，通常是单链表为空或者只有一个结点时，这时很容易求解，从而得到递归出口。

  【例2.6】有一个不带头结点的单链表L，设计一个算法释放其中所有结点。

  ​ 解：设$L={a_1，a_2，…，a_n}，f(L)的功能是释放a_1～a_n$的所有结点，则f(L->next)的功能是释放$a_2～a_n$的所有结点，前者是“大问题”，后者是“小问题”。 ​ 假设f(L->next)是已实现，则f(L)就可以采用先调用f(L->next)，然后释放L所指结点来求解。

• 对应的递归模型如下：

  f(L) ≡不做任何事件		    当L=NULL时
  f(L) ≡ f(L->next); 释放*L结点    其他情况

• 对应代码如下：

  void DestroyList(LinkNode *&L)
  //释放单链表L中所有结点
  {  if (L!=NULL)
     {	DestroyList(L->next);
      free(L);
     }
  }

  二叉树的递归算法设计

  ​ 二叉树是一种典型的递归数据结构，当一棵二叉树采用二叉链表b存储时： ​ 设求解以b为根结点的整个二叉树的某功能为“大问题”。 ​ 求解其左、右子树的相同功能为“小问题”。 ​ 由大小问题之间的解关系得到递归体。 ​ 再考虑特殊情况，通常是二叉树为空或者只有一个结点时，这时很容易求解，从而得到递归出口。

  【例2.8】对于含n（n>0）个结点的二叉树，所有结点值为int类型，设计一个算法由其先序序列a和中序序列b创建对应的二叉链存储结构。

  BTNode *CreateBTree(ElemType a[],ElemType b[],int n) 
  //由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链存储结构bt
  {   int k;
      if (n<=0) return NULL;
      ElemType root=a[0];				//根结点值
      BTNode *bt=(BTNode *)malloc(sizeof(BTNode));
      bt->data=root;
      for (k=0;k<n;k++)			//在b中查找b[k]=root的根结点
         if (b[k]==root)
          break;
                            //a[1]…a[k]  b[0]…b[k-1]
      bt->lchild=CreateBTree(a+1,b,k);	        //递归创建左子树
              //a[k+1]…a[n-1]  b[k+1]…b[n-1] n-1-(k+1)+1=n-k-1
      bt->rchild=CreateBTree(a+k+1,b+k+1,n-k-1);//递归创建右子树
      return bt;
  }
  

  【例2.10】假设二叉树采用二叉链存储结构，设计一个递归算法由二叉树bt复制产生另一棵二叉树bt1。

  ​ 解：设f(bt，bt1)的功能是由二叉树bt复制产生另一棵二叉树bt1，它是“大问题”，则f(bt->lchild，bt1->lchild)的功能就是由bt的左子树复制产生bt1的左子树，f(bt->rchild，bt1->rchild)的功能就是由bt的右子树复制产生bt1的右子树，它们是“小问题”。

• 对应递归模型

  f(bt，bt1)  bt1=NULL				当bt=NULL时
  f(bt，bt1)  由bt结点复制产生bt1结点;		其他情况
          f(bt->lchild，bt1->lchild);
   		f(bt->rchild，bt1->rchild) 
  

• 对应递归算法

  void CopyBTree(BTNode *bt,BTNode *&bt1)
  //由二叉树bt复制产生bt1
  {  if (bt==NULL)
      bt1=NULL;
     else
     {	bt1=(BTNode *)malloc(sizeof(BTNode));
      bt1->data=bt->data;
      CopyBTree(bt->lchild,bt1->lchild);
      CopyBTree(bt->rchild,bt1->rchild);
     }
  }
  

递归算法设计实例

简单选择排序和冒泡排序

【问题描述】对于给定的含有n个元素的数组a，分别采用简单选择排序和冒泡排序方法对其按元素值递增排序。

简单选择排序

• 设f(a，n，i)用于对a[i…n-1]元素序列（共n-i个元素）进行简单选择排序，是“大问题”. f(a，n，i+1)用于对a[i+1…n-1]元素序列（共n-i-1个元素）进行简单选择排序，是“小问题”。 当i=n-1时所有元素有序，算法结束。

  • 递归模型

    $$\begin{aligned} &f(a，n，i) \equiv 不做任何事情，算法结束 当i=n-1\\ &f(a，n，i) \equiv 通过简单比较挑选a[i..n-1]中的最\\ & 小元素a[k]放在a[i]处; 否则\\ & f(a，n，i+1);\\ \end{aligned}$$

  • 递归算法

    void SelectSort(int a[]，int n，int i)
    {   int j，k;
        if (i==n-1) return;	//满足递归出口条件
        else
    　　{	k=i;			//k记录a[i..n-1]中最小元素的下标
        for (j=i+1;j<n;j++)  	//在a[i..n-1]中找最小元素
        　　if (a[j]<a[k])
            k=j;
        if (k!=i)		//若最小元素不是a[i]
            swap(a[i],a[k]);	//a[i]和a[k]交换
        SelectSort(a，n，i+1);
    　　}
    }//参照SelectSort.cpp
    

冒泡排序

• 设f(a，n，i)用于对a[i…n-1]元素序列（共n-i个元素）进行冒泡排序，是“大问题”，则f(a，n，i+1)用于对a[i+1…n-1]元素序列（共n-i-1个元素）进行冒泡排序，是“小问题”。当i=n-1时所有元素有序，算法结束。

  • 递归模型

    $$\begin{aligned} &f(a，n，i) \equiv 不做任何事情，算法结束 当i=n-1\\ &f(a，n，i) \equiv 对a[i..n-1]元素序列，从a[n-1]开始\\ & 进行相邻元素比较; 否则\\ & 若相邻两元素反序则将两者交换;\\ & 若没有交换则返回，否则执行f(a，n，i+1);\\ \end{aligned}$$

  • 递归函数

    void BubbleSort(int a[]，int n，int i)
    {   int  j;
        bool exchange;
        if (i==n-1) return;		//满足递归出口条件
    　　else
    　　{   exchange=false;		//置exchange为false
    　　　  for (j=n-1;j>i;j--)
    　　　　　　if (a[j]<a[j-1])		//当相邻元素反序时
    　　　　　　{	　swap(a[j],a[j-1]);
            　exchange=true;	//发生交换置exchange为true
    　　　　　　}
    　　　　if (exchange==false)		//未发生交换时直接返回　　　
    　　　　　　return;
    　　　　else				//发生交换时继续递归调用
    　　　　　　BubbleSort(a，n，i+1);
    　　}
    } }//参照BubbleSort.cpp
    
    

求解n皇后问题

• 【问题描述】在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。如下图所示是6皇后问题的一个解。

q[1…6]={2，4，6，1，3，5}

• 问题求解

​ 对于(i，j)位置上的皇后，是否与已放好的皇后(k，q[k])（1≤k≤i-1）有冲突呢？

• 显然它们不同列，若同列则有：q[k]==j；

• 对角线有两条，若它们在任一条对角线上，则构成一个等腰直角三角形，即|q[k]-j|==|i-k|。

(q[k]==j) || (abs(q[k]-j)==abs(i-k))

设queen(i，n)是在1～i-1行上已经放好了i-1个皇后，用于在i～n行放置n-i+1个皇后，则queen(i+1，n)表示在1～i行上已经放好了i个皇后，用于在i+1～n行放置n-i个皇后。 　　queen(i+1，n)比queen(i，n)少放置一个皇后。所以queen(i+1，n)是“小问题”，queen(i，n)是“大问题”。

• 递归模型

  $$\begin{aligned} &queen(i，n) \equiv n个皇后放置完毕，输出一个解 若i>n\\ &queen(i，n) \equiv 在第i行的合适的位置（i,j） 其他情况\\ & 在其上放置一个皇后;\\ & queen(i+1，n);\\ \end{aligned}$$

• 递归算法

  bool place(int i,int j)		//测试(i,j)位置能否摆放皇后
  {   if (i==1) return true;		//第一个皇后总是可以放置
      int k=1;
      while (k<i)			//k=1～i-1是已放置了皇后的行
      {	if ((q[k]==j) || (abs(q[k]-j)==abs(i-k)))
          return false;
      k++;
      }
      return true;
  }
  //已经在1~i-1行上放好i-1个皇后， queen( i, n)准备在i~n行放置n-i+1个皇后void queen(int i,int n)      
  {   if (i>n) 
      dispasolution(n);		//所有皇后放置结束
      else
      {	for (int j=1;j<=n;j++)	//在第i行上试探每一个列j
          if (place(i,j))		//在第i行上找到一个合适位置(i,j)
          {	q[i]=j;
          queen(i+1,n);
          }
      }
  }
  

  • 执行一次结果如下

    皇后问题(n<20) n=6↙ 6皇后问题求解如下： 第1个解：(1，2) (2，4) (3，6) (4，1) (5，3) (6，5) 第2个解：(1，3) (2，6) (3，2) (4，5) (5，1) (6，4) 第3个解：(1，4) (2，1) (3，5) (4，2) (5，6) (6，3) 第4个解：(1，5) (2，3) (3，1) (4，6) (5，4) (6，2)