在定义一个过程或函数时出现调用本过程或本函数的成分称为递归（ $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)
		prin

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/852761

【数据结构】CH5 递归_设计两个递归算法,maxnode(linknode *l)返回单链表l中的最大结点值,minnode

前言

一、什么是递归

1.递归的定义