递归的概念递归的定义 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个算法直接地或间接地调用自己,则称这个算法是递归的算法。
在以下三种情况下，常常用到递归方法。
定义是递归的
数据结构是递归的
问题的解法是递归的计算机学院信息教研室
DS
计算机学院信息教研室
DS
递归函数的定义一个算法可以分解成若干相同的小算法分解到某简单的子算法时终止有 一个或几个终止条件递归：由其前面的值求当前值递归必须导致终止条件定义是递归的求解阶乘函数的递归算法
long Factorial ( long n )
{
if ( n == 0 ) return 1;
else return n*Factorial (n-1);
}
例如，阶乘函数

时当时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 n! 的过程计算斐波那契数列的函数 Fib(n)的定义求解斐波那契数列的递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}

1),2()1(
0,1,
)(
nnF i bnF i b
nn
nF i b
数据结构是递归的搜索链表最后一个结点并打印其数值
template <class T>
void Find ( ListNode<T> *p)
{
if ( p → next == NULL )
cout << p → data << endl;
else Find ( p→ next );
}
例如，单链表结构在链表中寻找等于给定值的结点并打印其数值
template <class T> void Print ( ListNode<Type>
*p)
{
if ( p!= NULL)
if ( p → data == x )
cout << p→ data << endl;
else Print ( p→ next );
}
递归算法的设计设计思想,分而治之原问题 子问题最终可直接求解计算机学院信息教研室
DS
设计递归出口问题的解法是递归的例如，汉诺塔 (Tower of Hanoi)问题汉诺塔问题
A
B
C
汉诺塔问题
A
B
C
汉诺塔问题 将 A塔上的金盘移到 B塔上
！要求 一次只能移动一个盘大盘不能压小盘
A
B
C
汉诺塔问题 第一次
A
B
C
汉诺塔问题 第二次
A
B
C
汉诺塔问题 第三次
A
B
C
汉诺塔问题 第四次
A
B
C
汉诺塔问题 第五次
A
B
C
汉诺塔问题 第六次
A
B
C
汉诺塔问题 第七次
A
B
C
6.3 递归过程与递归工作栈递归过程在实现时，需要自己调用自己。
每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。
层层向下递归，退出时的次序正好相反：
递归次序
n! (n-1)! (n-2)! 1! 0!=1
返回次序因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。
非递归函数调用时要保存信息
（ 1）返回地址
（ 2）本函数调用时与形参结合的实参值
（ 3）本函数的局部变量计算机学院信息教研室
DS
递归函数调用时也要保存以上信息由于是自调用，返回地址、实参值和局部变量等互相重叠，不能使用可考虑用递归工作栈来保存这些信息函数递归时的活动记录计算 Factorial时活动记录的内容斐波那契数列的递归调用树本章小结学习要点：
a)、熟悉递归的概念；
b),掌握递归设计的思想、方法 ；
c)、熟悉递归过程和递归工作栈。