河池学院：《数据结构》课程电子教案（PPT教学课件）第5章 递归

第5章递归 5.1什么是递归 提纲 5.2递归算法的设计 CONTENTS 作业 上机实验题 1/66

CONTENTS 提纲 1/66

在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。 若调用自身，称之为直接递归。 若过程或函数A调用过程或函数B，而B又调用A，称之为间接递归。 在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所 以主要讨论直接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，称为 尾递归。 2/66

【例5.1】以下是求n!（n为正整数）的递归函数。它属于什么类型的递归。 int fun(int n) { if (n==1) //语句1 return(1); //语句2 else //语句3 return(fun(n-1)*n); //语句4 } 解：直接递归函数。又由于递归调用是最后一条语句，所以它 又属于尾递归。 3/66

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

一般来说，能够用递归解决的问题应该满足以下3个条件： 需要解决的问题可以转化为一个或多个子问题来求解，而这些子 问题的求解方法与原问题完全相同，只是在数量规模上不同。 递归调用的次数必须是有限的。 必须有结束递归的条件来终止递归。 5/66

1. 定义是递归的 有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci （斐波那契）数列等。 int Fib1(int n) //求Fibonacci数列的第n项 { if (n==1 || n==2) return 1; else return Fib1(n-1)+Fib1(n-2); } 6/66

2. 数据结构是递归的 有些数据结构是递归的。如单链表就是一种递归数据结构。 class LinkNode //单链表结点泛型类 { E data; LinkNode next; //下一个结点的指针 public LinkNode() //构造方法 { next=null; } public LinkNode(E d) //重载构造方法 { data=d; next=null; } } head=（a1,head.next） head a1 a2 . an ∧ head.next也是一个单链表 不带头结点单链表 7/66

示例 求一个不带头结点单链表p中所有data成员（假设为int型）之和。 public static int Sum(LinkNode p) { if (p==null) return 0; else return(p.data+Sum(p.next)); } p a1 a2 . an ∧ p.next 8/66

3. 问题的求解方法是递归的 Hanoi问题 设Hanoi(n，x，y，z)表示将n个盘片从x塔座借助y塔座移动到z塔座上: Hanoi(n，x，y，z) Hanoi(n-1，x，z，y)； move(n，x，z)：将第n个圆盘从x移到z； Hanoi(n-1，y，x，z) 9/66

public static void Hanoi(int n,char X,char Y,char Z) { if (n==1) //只有一个盘片的情况 System.out.printf("将第%d个盘片从%c移动到%c\n",n,X,Z); else //有两个或多个盘片的情况 { Hanoi(n-1,X,Z,Y); System.out.printf("将第%d个盘片从%c移动到%c\n",n,X,Z); Hanoi(n-1,Y,X,Z); } } 10/66