《数据结构》课程教学资源：第六章 递归

第σ章邁妇 61什么是递归 62递归調用的实视原理 本章小结

启迪管理课程 第6章 递归 6.1 什么是递归 6.2 递归调用的实现原理 本章小结

61什么是递归 6.,1递归的定义 在定义一个过程或函数时出现调用本过 程或本函数的成分称之为递归。若调用自身, 称之为直接递归。若过程或函数p调用过程 或函数q,而q又调用p,称之为间接递归

启迪管理课程 6.1.1 递归的定义 在定义一个过程或函数时出现调用本过 程或本函数的成分,称之为递归。若调用自身, 称之为直接递归。若过程或函数p调用过程 或函数q,而q又调用p,称之为间接递归。 6.1 什么是递归

61什么是递归 例61以下是求m(m为正整数)的递归函数。 int fun(int n) int x; if(n==1) 体语句1*/ return(1); 语句2*/ else /语句3 return(fun(n-1)*n);/语句4*/ 在该函数fun(n)求解过程中,直接调用fun(n-1)(语 句4)自身,所以它是一个直接递归函数。又由于递归调 用是最后一条语句,所以它又属于尾递归。 3

启迪管理课程 例6.1 以下是求n!(n为正整数)的递归函数。 6.1 什么是递归 int fun(int n) { int x; if (n==1) /*语句1*/ return (1); /*语句2*/ else /*语句3*/ return(fun(n-1)*n); /*语句4*/ } 在该函数fun(n)求解过程中,直接调用fun(n-1)(语 句4)自身,所以它是一个直接递归函数。又由于递归调 用是最后一条语句,所以它又属于尾递归

61什么是递归 61.2何时使用递归 递归使用的场合有如下三种: 1.定义是递归的 数学公式、数列等的定义是递归的,例: f()=f(-1)+f(-2)f(1)=f(2)=1 这些问题的求解过程可以将其递归定义直接 转化为对应的递归算法

启迪管理课程 6.1.2 何时使用递归 递归使用的场合有如下三种： 1. 定义是递归的 数学公式、数列等的定义是递归的，例： 这些问题的求解过程可以将其递归定义直接 转化为对应的递归算法。 n! (n  1)!*n n  1时， n! 1 f(n)f(n1)f(n2) f(1)f(2)1 6.1 什么是递归

61什么是递归 2.数据结构是递归的 有些数据结构是递归的。例如,单链表就是一种递 归数据结构,其结点类型定义如下: typedef struct LNode Elem Type data; struct LNode *next 3 Linklist; 该定义中结构体 LNode的定义中用到了它自身,即 指针域next是一种指向自身类型的指针,所以它是一种 递归数据结构 5

启迪管理课程 2. 数据结构是递归的 有些数据结构是递归的。例如, 单链表就是一种递 归数据结构,其结点类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LinkList; 该定义中,结构体LNode的定义中用到了它自身,即 指针域next是一种指向自身类型的指针,所以它是一种 递归数据结构。 6.1 什么是递归

61什么是递归 求一个不带头结点的单链表head的所有data域(假设为 int型)之和的递归算法如下 head a 非递归的算法: head; sum=0; while(p!-nullsum=sum+p->data; p=p->next 递归算法 int Sum Linklist *head) if (head==null return 0 else return (head->data+ Sum(head->next) 6

启迪管理课程 求一个不带头结点的单链表head的所有data域(假设为 int型)之和的递归算法如下： int Sum(LinkList *head) { if (head==NULL) return 0; else return(head->data+Sum(head->next)); } head a1 a2 …... an ^ 非递归的算法： p=head; sum=0; while (p!=NULL) {sum=sum+p->data; p=p->next;} 6.1 什么是递归 递归算法：

61什么是递归 3.问题的求解方法是递归的 典型的有Hano问题求解 设:有X、Y、Z三个塔座,在X上按直径大小递减次序依次插 有n个直径各不相同的圆盘,各圆盘按直径从小到大编为1-n 要求:将X塔上的n个圆盘按规则移至Z上,并仍按同样顺序 叠排 移动规则:①每次只能移动一个圆盘:②移动的圆盘可以插 在任一塔座上,但是在任一时刻都不能将大盘压在小盘上

启迪管理课程 3. 问题的求解方法是递归的 典型的有Hanoi问题求解 6.1 什么是递归

61什么是递归 例:计算两个非负整数a*b的算法 1.迭代方式:a=a个b之和2.递归方式:a中=b+(a-1)畅 int Mull(int a, int b) int Mul2(int a, int b) i int i, c=0; i if(a==0)return 0 for(i=0; i<a; i++) else return(b+Mul2(a-1, b c+=b: return c. 8

启迪管理课程 6.1 什么是递归 例：计算两个非负整数a*b的算法 int Mul1(int a, int b) { int i,c=0; for(i=0;i<a;i++) c+=b; return c; } 1.迭代方式：a*b=a个b之和 2.递归方式：a*b=b+(a-1)*b int Mul2(int a, int b) { if(a==0) return 0; else return(b+Mul2(a-1,b) }

61什么是递归 △→递归的关键点: ①用较简单的新问题来表示较复杂的原问题。例如 n!=n(n-1)!或n!=(n+1)!/(n+1)前者(n-1)!较n! 简单,可行;后者(n+1)!较n!更复杂,不可行。 ②不能产生自己调用自己的无穷序列,即必须有一 个递归调用序列的“出口”,来终止递归调用。 △递归的实现:递归过程都是通过栈来实现的, 并且任何递归算法均可通过栈改写为非递归算 法

启迪管理课程 6.1 什么是递归 !递归的关键点： !递归的实现：递归过程都是通过栈来实现的， 并且任何递归算法均可通过栈改写为非递归算 法。 ①用较简单的新问题来表示较复杂的原问题。例如 n!=n(n-1)!或n!=(n+1)!/(n+1) 前者(n-1)!较n! 简单，可行；后者(n+1)!较n!更复杂，不可行。 ②不能产生自己调用自己的无穷序列，即必须有一 个递归调用序列的“出口” ，来终止递归调用

61什么是递归 递归的特点:是程序设计的一个强有力的工 具,它具有结构清晰,程序易编、易读、易 调试,程序正确性易证明等优点;但运行效 率低。 △递归基本原理:是重复地把问题转化为与原 问题相似的新问题,直到问题可以解决为止 10

启迪管理课程 6.1 什么是递归 !递归的特点：是程序设计的一个强有力的工 具，它具有结构清晰，程序易编、易读、易 调试，程序正确性易证明等优点；但运行效 率低。 !递归基本原理：是重复地把问题转化为与原 问题相似的新问题，直到问题可以解决为止