递归第5章5.1什么是递归5.2递归调用的实现原理5.3递归算法的设计
1 第5章 递归 5.3 递归算法的设计 5.1 什么是递归 5.2 递归调用的实现原理
6.1什么是递归递归的定义6.1.1在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数p调用过程或函数q，而又调用p，称之为间接递归如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为屋递归2
2 6.1 什么是递归 6.1.1 递归的定义 在定义一个过程或函数时出现调用本过程或本 函数的成分，称之为递归。若调用自身，称之为 直接递归。若过程或函数p调用过程或函数q，而q 又调用p，称之为间接递归。 如果一个递归过程或递归函数中递归调用语 句是最后一条执行语句，则称这种递归调用为尾 递归
例6.1以下是求n！（n为正整数）的递归函数int fun(int n)int x;/*语句1*/if (n==1)/*语句2*/x=1;/*语句3*/else/*语句4*/x=fun(n-1)*n;/*语句5*/return(x);在该函数fun(n)求解过程中，直接调用fun(n-1)（语句4）自身，所以它是一个直接递归函数。又由于递归调用是最后一条语句，所以它又属于尾递归3
3 例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.定义是递归的2.数据结构是递归的3.问题的求解方法是递归的
4 6.1.2 何时使用递归 以下三种情况常常要用到递归的方法。 2. 数据结构是递归的 3. 问题的求解方法是递归的 1. 定义是递归的
1.定义是递归的有许多数学公式、数列等的定义是递归的。例如，求n！和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。(1)fun(n)(2)n*fun(n-1)n>15
5 1. 定义是递归的 有许多数学公式、数列等的定义是递归的。 例如，求n!和Fibonacci数列等。这些问题的求解 过程可以将其递归定义直接转化为对应的递归算 法。 fun(n)= 1 (1) n*fun(n-1) n>1 (2)