1《数据结构》国家精品课程24/12/23第六章递归6.1递归的概念6.2基本递归过程6.3递归过程的实现与堆栈2《数据结构》国家精品课程24/12/23定义：如果一个对象部分地包含它自己，或者利用自己定义自己的方式来定义或描述，则称这个对象是递归的（递归定义）；如果一个过程直接或间接地调用自己，则称这个过程是一个递归过程（递归算法）。组成：递归部分、终止条件(递归出口)6.1递归的概念3《数据结构》国家精品课程24/12/23递归的例子xn=x*x*…*x*x（幂函数）P(1)=x递归出口P(n)=P(n-1)*x,n>1递归部分S(n)=1+2+3+…+(n-1)+nS(1)=1递归出口S(n)=S(n-1)+n,n>1递归部分4《数据结构》国家精品课程24/12/23以下三种情况适于用递归求解问题：1.问题的定义是递归的；2.问题所涉及的数据结构是递归的；3.问题的解法满足递归的性质。5《数据结构》国家精品课程24/12/231、问题的定义是递归的阶乘函数、幂函数和斐波那契数列。[例1]阶乘函数的定义6《数据结构》国家精品课程24/12/23求解阶乘函数的递归过程longFactorial(longn){if(n==0)return1;//递归终止条件elsereturnn*Factorial(n-1);}//递归调用过程7《数据结构》国家精品课程24/12/23[例2]斐波那契数列Fib(n)的定义求解斐波那契数列的递归算法longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}8《数据结构》国家精品课程24/12/232、问题所涉及的数据结构是递归的[例1]单链表节点类的递归定义template
classNode{private:Node*next;public:Tdata;……}datadatanextnext9《数据结构》国家精品课程24/12/23[例2]单链表的递归定义head=NULL头指针为head的单链表的递归定义：（1）head指向一个空结点的数据结构是一个单链表（2）head指向一个非空结点，该结点的指针域指向一个单链表，这样的数据结构是一个单链表。7245…head36∧10《数据结构》国家精品课程24/12/23头指针为p的单链表中搜索链表最后一个结点并打印其数值templatevoidFind(Node*p){if(p→next==NULL)cout<
