计算机程序设计基础 第六饼递归
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