第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是一种指向自身类型的指针，所以它是 一种递归数据结构