第σ章邁妇 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(n1)f(n2) 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 什么是递归