2021年递归与回溯.ppt

重点内容
递归的概念
递归的表示
递归实现方法
用递归实现简单回溯算法
实现递归时应注意的几个方面
递归与递推的区别和联系
递归与回溯
2021/1/15
1
递归的概念
先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之为递归。
一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。
递归与回溯
2021/1/15
2
递归的特点与应用场合
用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。
递归与回溯
2021/1/15
3
递归的实现方法
递归是借助于一个递归工作栈来实现.
: 问题向一极推进，这一过程叫做递推；这一过程相当于压栈.
: 问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈.
递归与回溯
2021/1/15
4
一个简单的实例
将n个不同颜色的球,分别放到n个不同的盒子中去,问有多少种放法?
分析:
显然所有的方法数为 n!
这样,对于任意输入的整数n,我们只要算出n!即可．
设f(n)=n!,则有，
递归与回溯
2021/1/15
5
用递归实现
Var n :integer; t:longint;
function f (n:integer):longint;
begin
if n=0 then f:=1
else f:=n*f (n-1)
end;
begin
write(‘n=’);readln(n);
t:=f (n);
writeln(‘n!=’,t);
end.
递归与回溯
2021/1/15
6
N=3时的递归过程
递归与回溯
2021/1/15
7
递归与回溯
2021/1/15
8
递归与回溯
2021/1/15
9
递归的表示
Hanoi塔问题
进制转换问题
快速排序
归并排序
Ｎ皇后问题
背包问题
地图着色问题
……
递归与回溯
2021/1/15
10