【数据结构】CH5 递归

在定义一个过程或函数时出现调用本过程或本函数的成分称为

递归

（
$recursion$
）。若调用自身，称为

直接递归

（
$direct$
$recursion$
）。若过程或函数p调用过程或函数q，而q又调用p，称为

间接递归

（
$indirect$
$recursion$
）。如果一个递归过程或递归函数中的递归调用语句是

最后一条执行语句

，则称这种递归调用为

尾递归

（
$tail$
$recursion$
）。

递归不仅是数学中的一个重要概念，也是计算技术中的重要概念之一。在计算技术中，与递归有关的概念有递归数列、递归过程、递归算法、递归程序和递归方法等。

递归数列：有递归关系确定的数列
递归过程：直接或间接调用自身的过程
递归算法：包含递归过程的算法
递归程序：直接或间接调用自身的程序
递归方法：一种在有限步骤内根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元素（如数或函数）的方法

（2）【例5.1】以下是求n！（n为正整数）的递归函数，它属于什么类型的递归？

int fun(int n)
{
	if(n==1)
		return 1;
	else
		return(fun(n-1)*n);
}

直接递归函数&尾递归

（3）递归的优点&缺点

递归算法通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解，递归策略只需少量代码就可以描述出解题过程中所需要的多次重复计算，大大减少了算法的代码量。

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

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

递归算法的优点是结构简单、清晰、易于阅读，方便其正确性证明；缺点是在算法执行中占用的内存空间较多，执行效率低，不容易优化。

2.何时使用递归

（1）定义是递归的

有许多数学公式、数列等的定义是递归的。例如，求n！和
$Fibonacci$
数列等。对于这些问题的求解可以将其递归定义直接转化为对应的递归算法。例如，n！可以转化为【例5.1】的递归算法，求
$Fibonacci$
数列的递归算法如下：

int Fib1(int n)
{
	if(n==1||n==2)
		return(1);
	else
		return(Fib1(n-1)+Fib1(n-2));
}

（2）数据结构是递归的

有些数据结构是递归的。例如第二章中介绍的单链表就是一种递归数据结构，其结点类型声明如下：

typedef struct LNode
{
	Elemtype data;	//存放结点数据
	srtuct LNode *next;	//指向下一个同类型结点的指针
}LinkNode;	//单链表的结点类型

其中，LNode的声明用到了它自身，即指针域next是一种指向自身类型结点的指针，所以它是一种递归数据结构。

对于递归数据结构，采用递归的方法编写算法既方便又高效。例如求一个

不带头结点

的单链表L的所有data域（假设为int型）之和的递归算法如下：

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

单链表数据结构中输出所有数据元素（无头结点）的算法如下：

display(LinkList *list)
{
	if(list!=NULL)
	{
		printf("%d",list->data);
		display(list->next);
	}
}

（3）问题的求解方法是递归的

有些问题的解法是递归的，典型的有

Hanoi问题

求解，该问题的描述是，设有3个分别命名为X、Y和Z的塔座，在塔X上有n个直径各不相同的盘片，从小到大依次编号为1、2、……、你。现要求将X塔座上的这n个盘片移到塔座Z上并仍按同样的顺序叠放，盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X、Y和Z中的任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计求解该问题的算法。

Hanoi问题特别适用采用递归方法来求解。设Hanoi(x,y,z)表示将n个盘子从x塔借助y塔移动到z塔上，递归分解的过程如下：

其含义是首先将x塔座上的n-1个盘片借助z塔座移动到y塔座上；此时x塔座上只有一个盘片，将其直接移动到z塔座上；再将y塔座上的n-1个盘片借助x塔座移动到z塔座上。由此得到Hanoi1递归算法如下：

void Hanoi1(int n,char X,char Y,char Z)
{
	if(n==1)
		printf("\t将第%d个盘子从%c移动到&c\n",X,Z);
	else
	{
		Hanoi1(n-1,X,Z,Y);
		pirntf("\t将第%d个盘子从%c移动到&c\n",n,X,Z);
		Hanoi1(n-1,Y,X,Z);
	}
}

3.递归模型

递归模型是递归算法的抽象，它反应一个递归问题的递归结构。例如，【例5.1】的递归算法对应的递归模型如下：

f(n)=1 n=1

f(n)=n*f(n-1) n>1

其中，第一个式子给出了递归的终止条件，第二个式子给出了f(n)的值与f(n-1)的值之间的关系。把第一个式子称为

递归出口

，第二个式子称为

递归体

。

一般情况下，

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

。递归出口确定递归到何时结束，即指出明确的递归结束条件。递归体确定递归求解时的递推关系。

递归出口的一般格式为：
$f(s_{1})=m_{1}$
。这里，
$s_{1},m_{1}$
均为常量，有些递归问题可能有几个递归出口。递归体的一般格式如下：

$f(s_{n})=g(f(s_{i}),f(s_{i+1}),\cdots,f(s_{n-1}),c_{j},c_{j+1},\cdots,c_{m})$

其中，
$n,i,j,m$
均为正整数。这里的
$s_{n}$
是一个递归“大问题”，
$s_{i},s_{i+1},\cdots,s_{n-1}$
为递归“小问题”，
$c_{j},c_{j+1},\cdots,c_{m}$
是若干个可以直接（用非递归方法）解决的问题，
$g$
是一个非递归函数，可以直接求值。

实际上，递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直到每个“小问题”都可以直接解决（此时分解到递归出口）。但

递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似

。

为了讨论方便，设简化的递归模型（即将一个“大问题”分解为一个“小问题”）如下：

$f(s_{1})=m_{1}$

$f(s_{n})=g(f(s_{n-1}),c_{n-1})$

在求
$f(s_{n})$
时的分解过程如下：

一旦遇到递归出口，分解过程结束，开始求值过程，所以分解过程是“量变”过程，即原来的“大问题”在慢慢变小，但尚未解决，遇到递归出口后便发生了“质变”，即原递归问题便转化成直接问题。上面的求值过程如下：

这样，
$f(s_{n})$
便计算出来了。因此，递归的执行过程由分解和求值两部分构成，分解部分就是用递归体将“大问题”分解成“小问题”，直到递归出口为止，然后进行求值过程，即已知“小问题”计算“大问题”。前面的
$fun(5)$
的求解过程如下：

在递归算法执行中最长的递归调用的链长称为该算法的递归调用深度。例如，求n！对应的递归算法在求
$fun(5)$
时递归调用深度是5。

对于复杂的递归算法，其执行过程可能需要循环反复的分解和求值才能获得最终解。例如，对于前面求
$Fibonacci$
数列的Fib1算法，求Fib1(6)的过程构成的递归树如图5.4。向下的实箭头表示分解，向上的虚箭头表示求值，每个方框旁边的数字是该方框的求值结果，最后求得结果为8.带递归树的高度为5，所以递归调用深度也是5。

4.递归与数学归纳法

从递归体可以看到，如果已知
$s_{i},s_{i+1},\cdots,s_{n-1}$
，就可以确定
$s_{n}$
。从数学归纳法的角度来看，这相当于数学归纳法归纳步骤的内容。但仅有这个关系还不能确定这个数列，若使它完全确定，还应给出这个数列的初始值
$s_{1}$
。

例如，采用数学归纳法证明下式：

$1+2+\cdots+n=\frac{n(n+1)}{2}$

数学归纳法是一种论证方法，而递归是算法和程序设计的一种实现技术，数学归纳法是递归求解问题的理论基础。可以说递归的思想来自数学归纳法。

二、栈和递归

1.函数调用栈

函数调用操作包括从一块代码到另一块代码之间的双向数据传递和执行控制转移。数据传递通过函数参数和返回值实现，另外还需要在进入函数时为函数的局部变量分配存储空间，并且再退出函数时收回这部分空间。

大多数CPU上的程序实现使用栈来支持函数调用操作。单个函数调用操作所使用的函数调用栈被称为栈帧（
$stack$
$frame$
）结构。每次函数调用时都会相应的创建一帧，保存返回地址、函数实参和局部变量值等，并将该帧压入调用栈。若在该函数返回之前又发生了新的调用，则同样要将与新函数对应的一帧进栈，称为栈顶。函数一旦执行完毕，对应的帧便出栈，控制权交还给该函数的上层调用函数，并按照该帧中保存的返回地址确定程序中继续执行的位置。

例如，若有以下程序：

int main()
{
	int m,n;
	...
	f(m,n);	//后面第一个语句地址为d1
	...
	return 1;
}
void f(int s,int t)
{
	int i;
	...
	g(i);	//后面第一个语句地址为d2
	...
}
void g(int d)
{
	int x,y;
	...
}

在执行上述程序时，假设main函数的返回地址为
$d_{0}$
。当执行main函数时，将栈帧1进栈。在main函数中调用f函数时，将栈帧2进栈。在f函数中调用g函数时，将栈帧3进栈。当g函数执行完毕，控制权交回到f函数，转向其中的d2地址继续执行，将栈帧3退栈，其余执行结果类似。

2.递归调用的实现

递归是函数调用的一种特殊情况，即它是调用自身代码。因此，也可以把每一次递归调用理解成调用自身代码的一个复制件。由于每次调用时，它的参数和局部变量可能不同，因为也就保证了各个复制件执行时的独立性。

但这些调用在内部实现时并不是每次调用真正去复制一个复制件存放在内存中，而是采用代码共享的方式，也就是他们都是调用同一个函数的代码，系统为每一次调用开辟一组存储单元，用来存放本次调用的返回地址以及被中断的函数的参数值。这些单元以栈的形式存放每调用一次进栈一次，当返回时执行出栈操作，把当前栈顶保留的值送回相应的参数中进行恢复，并按栈顶中的返回地址从断电继续执行。下面通过计算fun(5)的值介绍递归调用过程实现的内部机理。

表5.1给出了求解fun(5)的递归调用过程中程序的执行及栈的变化情况，设调用fun(5)的返回地址为
$d_{0}$
。

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

在调用fun(5)时，先把返回地址
$d_{0}$
以及参数5进栈，然后执行语句1、3、4，当遇到其中的fun(5-1)（即fun(4)）时，必须中断当前执行的程序，转去调用fun(4)，记录下其返回地址为
$d_{1}$
；在调用fun(4)时，先把返回地址
$d_{1}$
以及参数4进栈，然后执行语句1、3、4，当遇到其中的fun(3)时，转去调用fun(3)，记录下其返回地址
$d_{2}$
；……。一直到调用fun(1)，把返回地址
$d_{4}$
以及参数1进栈。然后执行fun(1)，执行语句1、2，返回1并出栈一次；执行fun(2)，执行语句4，返回2并出栈一次；……。一直到执行fun(5)，此时栈空，返回120并转向
$d_{0}$
。

例如，已知程序如下：

int S(int n)
{
	return(n<=0)?0:S(n-1)+n;
}
int main()
{
	printf("%d\n",S(1));
	return 1;
}

程序执行时使用一个栈来保存调用过程的信息，这些信息用main()、S(0)和S(1)表示，那么自栈底到栈顶保存的信息的顺序是怎么样呢？

首先从main()开始执行程序，将main()信息进栈，遇到调用S(1)，将S(1)信息进栈，在执行递归函数S(1)时又遇到调用S(0)，再将S(0)信息进栈。所以，自栈底到栈顶保存的信息的顺序是
$main()\rightarrow S(1)\rightarrow S(0)$
。

3.递归到非递归的转换

（1）直接转换法

直接转换法就是用迭代方式或者循环语言替代多次重复的递归调用。
直接转换法通常用来消除尾递归和单项递归
如果一个递归函数中递归调用语句是最后一条执行语句且把当前运算结果放在参数里传给下层函数，称这种递归调用为

尾递归

。
单向递归

是指递归的求值过程总是朝着一个方向进行的

int fact(int n)
{
	if(n==1)
		return 1;
	else
		return n*fact(n-1);
}

int fact1(int n,int ans)
{
	if(n==1)
		return fact1(n-1,n*ans);
}

一般情况下，尾递归算法可以通过循环或者迭代方式转换为等价的非递归算法。例如，前面求
$Fibonacci$
数列的递归算法Fib1可以转换如下：

int Fib2(int n)
{
	int a=1,b=1,i,s;
	if(n==1||n==2)
		return 1;
	else
	{
		for(i=3;i<n;i++)
		{
			s=a+b;
			a=b;
			b=s;
		}
		return s;
	}
}

（2）间接转换法

其他相对复杂的递归算法不能直接求值，执行中需要回溯
可以在理解递归调用实现过程的基础上，用栈来模拟递归执行过程，即使用栈保存中间结果，从而将其转换为等效的非递归算法。称为间接转换法

对于不是尾递归的复杂递归算法，在理解递归调用实现过程的基础上可以用栈来模拟递归执行过程，从而将其转换为等价地非递归算法。

例如，在将前面求解Hanoi问题的递归算法Hanoi1转换为等价地非递归算法时，需要使用一个栈暂时存放还不能直接移动盘子的任务或子任务。

三、递归算法设计

1.相关概念

设计思想：寻找递归关系，确定递归出口
递归关系：将整个问题分解成若干个子问题，通过分别求解子问题，最后获得整个问题的解，其中部分子问题的解决方法和解决整个问题的方法一样，这就是递归关系
递归出口：整个问题分解成若干个子问题，子问题继续分解，如此反复进行，直到子问题无需再分解或不能再分解，直接得到结果时，这就是递归出口
递归算法的设计：首先判断是否满足出口条件，满足执行出口操作，否则用同样的方法解决子问题

2.例题

（1）采用递归算法求实数数组A[0..n-1]中的最小值

float f(float A[],int i)
{
	float m;
	if(i==0)
		return A[0];
	else
	{
		m=f(A,i-1);
		if(m>A[i])
			return A[i];
		else
			return m;
	}
}

（2）求含n（>1）个元素的顺序表L中的最大元素

//解法一：顺序表L采用数组data[0..n-1]存放全部元素，采用与（1）类似的思路
ElemType Max1(SqList L,int i)
{
	ElemType max;
	if(i==0)
		return L.data[0];
	else
	{
		max=Max1(L,i-1);
		if(max<L.data[i])
			return L.data[i];
		else
			return max;
	}
}
//解法二：将data数组分解成两个数组，分别求最大值，取两个最大值中的大者
ElemType Max2(SqList L,int i,int j)
{
	int mid;
	ElemType max,max1,max2;
	if(i==j)
		max=L.data[i];
	else
	{
		mid=(i+j)/2;
		max1=Max2(L,i,mid);
		max2=Max2(L,mid+1,j);
		max=(max1>max2)?max1:max2;
	}
	return(max);
}

（3）不带头结点的单链表的相关递推算法

求单链表中数据结点的个数

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

正向显示以L为首结点指针的单链表的所有节点值

void DispList(LinkList *L)
{
	if(L=NULL)
		return;
	printf("%d",L->data);
	DispList(L->next);
}

反向显示以L为首结点指针的单链表的所有节点值

void DispList(LinkList *L)
{
	if(L=NULL)
		return;
	DispList_re(L->next);
	printf("%d",L->data);
}

删除以L为首结点指针的单链表中值为x的第一个结点

bool ListDelette(LinkList *&L,ElemType)
{
	LinkList *t;
	if(L==NULL)
		return 0;
	if(L->data==e)
	{
		t=L;
		L=L->next;
		free(t);
		return 1;
	}
	else
		ListDelete(L->next,e);
}

删除以L为首结点指针的单链表中值为x的所有结点

bool ListDelette(LinkList *&L,ElemType)
{
	LinkList *t;
	if(L==NULL)
		return 0;
	if(L->data==e)
	{
		t=L;
		L=L->next;
		free(t);
		ListDelete(L,e);
	}
	else
		ListDelete(L->next,e);
}

输出以L为首结点指针的单链表中最大节点值

ElemType maxv(LinkList *L)
{
	ElemType m;
	if(L->next==NULL)
		return L->data;
	m=maxv(L->next);
	if(m>L->data)
		return m;
}

释放L为首结点指针的单链表的所有结点

void DestroyList(LinkList *&L)
{
	if(L==NULL)
		return;
	DestroyList(L->next);
	free(L);
}

（4）递归函数中的引用形参可以用全局变量代替

例如：1+2+……+n

void add(int n,int &s)
{
	int s1;
	if(n==1)
		s=1;
	else
	{
		add(n-1,s1);
		s=s1+n;
	}
}

int s=0;	//全局变量
void add1(int n)
{
	if(n==1)
		s=1;
	else
	{
		add1(n-1);
		s+=n;
	}
}

原文链接：https://blog.csdn.net/m0_72318954/article/details/127356680

前言

一、什么是递归

1.递归的定义

（1）相关定义