计算机程序设计基础 第六饼递归
1 计算机程序设计基础 第六讲 递归
递归及其实现 递归算法在可计算性理论中占有重要地位,它是算法 设计的有力工具,对于拓展编程思路非常有用。就 递归算法而言并不涉及高深数学知识,只不过初学 者要建立起递归概念不十分容易。 我们先从一个最简单的例子导入 用递归算法求n 定义:函数fact(m)=n! fac(n-1)=(n-1) 则有fact(m)=n.fact(n-1) 已知fac(1)=1
2 递归算法在可计算性理论中占有重要地位，它是算法 设计的有力工具，对于拓展编程思路非常有用。就 递归算法而言并不涉及高深数学知识，只不过初学 者要建立起递归概念不十分容易。 我们先从一个最简单的例子导入。 递归及其实现 用递归算法求n! 定义：函数 fact(n) = n! fact(n-1) = (n-1)! 则有 fact(n) = n fact(n-1) 已知 fact(1) = 1 •
为了表述得直观清晰,我们定义两个结点:或结点与 与结点。 图示的直观性与思维助力。 1、或结点 ○A 条件力条件zA ∫B,Z=me(真) C,z=ae(假) B○ A为“或结点”,A依不同条件会有两种不同的取值B或 C。结点用○表示
3 为了表述得直观清晰，我们定义两个结点：或结点与 与结点。 图示的直观性与思维助力。 1、或结点 , , B Z true A C Z false = = = （真） （假） A 条件 Z 条件!Z B C A为“或结点” ，A依不同条件会有两种不同的取值B或 C。结点用 表示
如果有多于2种取值,可用下图 条件为Z1,Z2,…,Zn,取值为B或C,…或G
4 如果有多于2种取值，可用下图： Z1 Z2 … Zn B C … G A 条件为Z1, Z2, …,Zn，取值为B或C,…或G
2、与结点 A 与结点要涂票,相关联 的B与C之间要用狐线 连起来。 B A为与结点,A的最终取值为C结点的值,但为了 求得C的值,得先求出B结点的值,C是B的函数
5 2、与结点 与结点要涂黑，相关联 的B与C之间要用弧线 连起来。 A为与结点，A的最终取值为C结点的值，但为了 求得C的值，得先求出B结点的值，C是B的函数。 A B C
仍以求m为例画出如下与或图 A fact(n) fac(1)=1 D A为或结点;B为直接可解结点,值为1; C为与结点,当n>1时,A的取值即C的值,而C的值即 E的值,为了求得E的值,需要先求出D的值。D值 fac(n-1)乘以n即为E的值
6 仍以求n!为例画出如下与或图 A为或结点；B为直接可解结点，值为1； C为与结点，当n>1时，A的取值即C的值，而C的值即 E的值，为了求得E的值，需要先求出D的值。D值 fact(n-1)乘以n即为E的值。 A fact(n) B fact(1)=1 C n=1 n>1 D fact(n-1) E n*fact(n-1)
与结点可能有多个相关联的点,这时可描述为下图 A结点的值最终为D的值,但为了求D需先求B和C。从 图上看先求左边的点才能求最右边的点的值,我们 约定最右边D点的值就是A结点的值
7 与结点可能有多个相关联的点，这时可描述为下图 A结点的值最终为D的值，但为了求D需先求B和C。从 图上看先求左边的点才能求最右边的点的值，我们 约定最右边D点的值就是A结点的值。 A B C D
下面我们以3!为例来画与或结点图,目的是体会递归 的含义。 fact(3) E D=2*C B fact(2) B=D=2 3 fact(2) E=3*B=3*2=6 A=E=6 2*fact( fact()
8 下面我们以3！为例来画与或结点图，目的是体会递归 的含义。 C = 1 D = 2*C = 2 B = D = 2 E = 3*B = 3*2 = 6 A = E = 6 1=1 1 3>1 B fact(2) 3*fact(2) fact(3) C fact(1) D 2*fact(1) A E 2>1
下面画出了调用和返回的递归示意图 A fact(3) B 3*fact(2) 2*act(1)通C 调 Afact(2) fact(1) =3* 2 返风 E
9 下面画出了调用和返回的递归示意图 B fact(2) =2*fact(1) =2*1 =2 返回 D A fact(3) =3*fact(2) =3*2 =6 E 返回 C fact(1) =1 调用 调用
从图可以想象: 欲求fact(3),先要求fact(2);要求act(2)先求act(1)。 就象剥一颗圆白菜,从外向里,一层层剥下来,到 了菜心,遇到1的阶乘,其值为1,到达了递归的边 界。然后再用act(m)= n facto(m-1)这个普遍公式,从 里向外倒推回去得到fac(n)的值 为了把这个问题说得再透彻一点。我们画了如下的流 程图:
10 从图可以想象： 欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1)。 就象剥一颗圆白菜，从外向里，一层层剥下来，到 了菜心，遇到1的阶乘，其值为1，到达了递归的边 界。然后再用fact(n)=n*fact(n-1)这个普遍公式，从 里向外倒推回去得到fact(n)的值。 为了把这个问题说得再透彻一点。我们画了如下的流 程图：