文档介绍：第5章递归
1)定义是递归的
2)数据结构是递归的
3)问题的解法是递归的
4 .利用栈实现的迷宫问题的非递归解法
(General List)
1)广义表的概念(LS)
2)广义表的性质
3)广义表的操作
4) 广义表的存储结构
5)广义表部分成员函数的实现算法
6) 广义表的递归算法
求广义表的深度、判断两个广义表相等否、广义表的复制算法
2/8/2018
1
第5章递归
n!=
1 n=0
n*(n-1)! n>0
若一个对象部分地包含它自己或用它自己给自己定义,则称这个对象是递归的。
若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。
*测试终结递归的条件递归出口
*n问题化为n-1问题(或着大问题化为小问题)
2/8/2018
2
三种常用到递归的方法
定义是递归的。
数据结构是递归的。
问题的解法是递归的。
1)定义是递归的
例1:如上面求n!的定义就是递归的。
long factorial(long n)
{ if(n==0)return 1;//递归终结条件
else return n*factorial(n-1);//n问题化为n-1问题
}
2/8/2018
3
下面看一下求factorial(3)
F(3) f(2) f(1) f(0)
n=3 n=2 n=1 n=0
6 n*f(2) n*f(1) n*f(0)
3*2 2*1 1*1
n=3 n=2 n=1
2/8/2018
4
例2 斐波那契数列(i)
0,1,1,2,3,5,8,……
以fn表示数列中第n个数,fn的递归定义:
n 当n=0,1时
Fib(n)=
Fib(n-1)+Fib(n-2) 当n>1时
long Fib(long n)
{
if(n<=1)return n;
else return Fib(n-1)+Fib(n-2);
}
2/8/2018
5
2)数据结构是递归的
链表就是一种递归数据结构。
data link
first 是一个单链表
first ……是一个单链表
指向的也是一个单链表
^
^
2/8/2018
6
数据结构是递归的,则写算法采用递归方法是最方便的。
。
template<class type>void find(listnode<type>*f)
{ if(f link==null) cout<<f data<<endL;
else find(f link);
}
,并输出之。
template<class type>void print(listnode<type>*f)
{ if(f!=null)
if(f data==x)cout<<f data<<endL;
else print(f link);
}
2/8/2018
7
3)问题的解法是递归的(Hanoi塔)
A B C
从A柱移到C柱:每次移一片盘,而且不允许大盘在小盘上。
分析:-1个盘由A B(递归)
C
-1个盘由B C(递归)
n
2/8/2018
8
#include <>
#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);//递归调用
}
}
2/8/2018
9
一个小型迷宫问题。
4 5 7
3 2 6
1
2/8/2018
10