第6章递归 6.1什么是递归 6.2递归法的设计 6.3递归算法到非递归犷法的转换 本章小结
第6章 递归 6.3 递归算法到非递归算法的转换 6.1 什么是递归 6.2 递归算法的设计 本章小结
6.1什么是递归 6.1.1递归的定义 在定义一个过程或函数时出现调用本过程或 本函数的成分,称之为递归。若调用自身,称之 为直接递归。若过程或函数p调用过程或函数q 而q又调用p,称之为回接递归。 如果一个递归过程或递归函数中递归调用语句 是最后一条执行语句,则称这种递归调用为尾递 归
6.1 什么是递归 6.1.1 递归的定义 在定义一个过程或函数时出现调用本过程或 本函数的成分，称之为递归。若调用自身，称之 为直接递归。若过程或函数p调用过程或函数q， 而q又调用p，称之为间接递归。 如果一个递归过程或递归函数中递归调用语句 是最后一条执行语句，则称这种递归调用为尾递 归
例61以下是求n!(n为正整数)的递归函数。 int fun (int n) int x; f(n==1) /语句1*/ X=1; /语句2*/ e /语句3 x=fun(n-1)*n; 语句4*/ return(x); /语句5*/ 在该函数fun(n求解过程中,直接调用fun(n-1)(语 句4)自身,所以它是一个直接递归函数。又由于递归 调用是最后一条语句,所以它又属于尾递归
例6.1 以下是求n!（n为正整数）的递归函数。 int fun(int n) { int x; if (n==1) /*语句1*/ x=1; /*语句2*/ else /*语句3*/ x=fun(n-1)*n; /*语句4*/ return(x); /*语句5*/ } 在该函数fun(n)求解过程中，直接调用fun(n-1)（语 句4）自身，所以它是一个直接递归函数。又由于递归 调用是最后一条语句，所以它又属于尾递归
6.1.2何时使用递归 在以下三种情况下,常常要用到递归的方法。 1.定义是递归的 有许多数学公式、数列等的定义是递归的。例如, 求n:和 Fibonacci数列等。这些问题的求解过程可以 将其递归定义直接转化为对应的递归算法
6.1.2 何时使用递归 在以下三种情况下，常常要用到递归的方法。 1. 定义是递归的 有许多数学公式、数列等的定义是递归的。例如， 求n!和Fibonacci数列等。这些问题的求解过程可以 将其递归定义直接转化为对应的递归算法
2.数据结构是递归的 有些数据结构是递归的。例如,第2章中介绍过的单 链表就是一种递归数据结构,其结点类型定义如下: typedef struct LNode ElemType data struct Node *next: 3 LinkList; 该定义中,结构体LNoe的定义中用到了它自身 即指针域next是一种指向自身类型的指针,所以它是 一种递归数据结构
2. 数据结构是递归的 有些数据结构是递归的。例如，第2章中介绍过的单 链表就是一种递归数据结构，其结点类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LinkList; 该定义中，结构体LNode的定义中用到了它自身， 即指针域next是一种指向自身类型的指针，所以它是 一种递归数据结构
对于递归数据结构,采用递归的方法编写算法既方 便又有效。例如,求一个不带头结点的单链表head的 所有data(假设为n型)之和的递归算法如下: int Sum(LinkList *head) if (head==NULL return 0: else return(head->data+Sum(head->next));
对于递归数据结构，采用递归的方法编写算法既方 便又有效。例如，求一个不带头结点的单链表head的 所有data域（假设为int型）之和的递归算法如下： int Sum(LinkList *head) { if (head==NULL) return 0; else return(head->data+Sum(head->next)); }
3.问题的求解方法是递归的 有些问题的解法是递归的,典型的有 Hanoi向题求 解,该问题描述是:设有3个分别命名为Ⅹ,Y和Z的 塔座,在塔座X上有n个直径各不相同,从小到大依 次编号为1,2,…,n的盘片,现要求将X塔座上的n 个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动 时必须遵守以下规则:每次只能移动一个盘片;盘片 可以插在X,Y和Z中任一塔座;任何时候都不能将 个较大的盘片放在较小的盘片上。设计递归求解算法 并将其转换为非递归算法 设 Hanoi(n,xyz)表示将n个盘片从x通过y移动到z上 递归分解的过程是:
3. 问题的求解方法是递归的 有些问题的解法是递归的，典型的有Hanoi问题求 解，该问题描述是：设有3个分别命名为X，Y和Z的 塔座，在塔座X上有n个直径各不相同，从小到大依 次编号为1，2，…，n的盘片，现要求将X塔座上的n 个盘片移到塔座Z上并仍按同样顺序叠放，盘片移动 时必须遵守以下规则：每次只能移动一个盘片；盘片 可以插在X，Y和Z中任一塔座；任何时候都不能将一 个较大的盘片放在较小的盘片上。设计递归求解算法， 并将其转换为非递归算法。 设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上， 递归分解的过程是：
Hanoi(n-1,x,z,y) Hanoi(n, x,y, z) move(n,x,z):将第n个圆盘从x移到z; Hanoi(n-l,y,x, 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)
6.1.3逆归模型 递归模型是递归算法的抽象,它反映一个递归向题的 递归结构,例如,前面的递归算法对应的递归模型如 下 fun(1)=1 fun(n=n*fun(n-1) n>1(2) 其中,第一个式子给出了递归的终止条件,第二个 式子给出了fum(n)的值与fun(m-1)的值之间的关系,我 们把第一个式子称为递归出口,把第二个式子称为递 归体
6.1.3 递归模型 递归模型是递归算法的抽象，它反映一个递归问题的 递归结构，例如，前面的递归算法对应的递归模型如 下： fun(1)=1 (1) fun(n)=n*fun(n-1) n>1 (2) 其中，第一个式子给出了递归的终止条件，第二个 式子给出了fun(n)的值与fun(n-1)的值之间的关系，我 们把第一个式子称为递归出口，把第二个式子称为递 归体
般地,一个递归模型是由递归出口和递归体两部分 组成,前者确定递归到何时结束,后者确定递归求解时 的递推关系。递归出口的一般格式如下 f(s1)= (6.1) 这里的s与m1均为常量,有些递归问题可能有几个递 归出口。递归体的一般格式如下: f(sn+1)=g(fs),fs+1)…,f(sn)cp+1x…,Cm (6.2) 其中,n,i,j,m均为正整数。这里的sn+是一个递 归“大问题” Ii+1 /.. ,s为递归“小问题”,c1 H1,…,Cm是若干个可以直接(用非递归方法)解决 的问题,g是一个非递归函数,可以直接求值
一般地，一个递归模型是由递归出口和递归体两部分 组成，前者确定递归到何时结束，后者确定递归求解时 的递推关系。递归出口的一般格式如下： f(s1 )=m1 (6.1) 这里的s1与m1均为常量，有些递归问题可能有几个递 归出口。递归体的一般格式如下： f(sn+1 )=g(f(si ),f(si+1 ),…,f(sn ),cj ,cj+1 ,…,cm) (6.2) 其中，n，i，j，m均为正整数。这里的sn+1是一个递 归“大问题” ，si，si+1，…，sn为递归“小问题” ，cj， cj+1，…，cm是若干个可以直接（用非递归方法）解决 的问题，g是一个非递归函数，可以直接求值