递归（Recuve）的概念汉诺塔（Tower of Hanoi）问题递归过.ppt

文档介绍：递归(Recurve)的概念
汉诺塔(Tower of Hanoi)问题
递归过程与递归工作栈
广义表(General Lists )
第四章递归
10/10/2018
1
递归的概念
递归的定义若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的;若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。
在以下三种情况下,常常用到递归方法。
定义是递归的
数据结构是递归的
问题的解法是递归的
10/10/2018
2
定义是递归的?
求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n*Factorial (n-1);
}
例如,阶乘函数
10/10/2018
3
求解阶乘 n! 的过程
10/10/2018
4
计算斐波那契数列的函数Fib(n)的定义
求解斐波那契数列的递归算法
long Fib ( long n ) { if ( n <= 1 ) return n;  else return Fib (n-1) + Fib (n-2);
}
10/10/2018
5
数据结构是递归的!
搜索链表最后一个结点并打印其数值
void Find ( ListNode *f )
{
if ( f →link == NULL )
cout << f →data << endl;
else Find ( f →link );
}
例如,单链表结构
10/10/2018
6
在链表中寻找等于给定值的结点并打印其数值void Print ( ListNode *f ) { if ( f != NULL) if ( f →data == x ) cout << f→data << endl; else Print ( f→link );}
10/10/2018
7
问题的解法是递归的

例如,汉诺塔(Tower of Hanoi)问题
10/10/2018
8
#include <>
void Hanoi (int n, String A, String B, String C )
{ //解决汉诺塔问题的算法
if ( n == 1 )
cout << " move " << A << " to " << C << endl;
else { Hanoi ( n-1, A, C, B );
cout << " move " << A << " to " << C<< endl;
Hanoi ( n-1, B, A, C ); }
}
10/10/2018
9
编写一个递归过程,它读入一串任意长的字符串,该串字符以“.”作为结束,要求打印出它们的倒序字符串。void reverse( ) { char ch; cin>>ch; if (ch!=‘.’) { reverse; cout << ch; }}
10/10/2018
10