20140501大学计算机程序与递归组合抽象构造分解.pptxVIP

计算系统与程序---程序的作用和本质;首先，设计并实现系统可以执行的基本动作(可实现的)，例如 “与”动作 “或”动作 “非”动作 “异或”动作 那么，复杂的动作呢？ 系统需要提供复杂的动作 复杂的动作千变万化 复杂的动作随使用者使用目的的不同而变化;指令：控制基本动作执行的命令;指令：控制基本动作执行的命令;基本动作 对基本动作的 抽象与控制 “与”动作 AND “或”动作 OR “非”动作 NOT;基本动作 对基本动作的 抽象与控制 “加”动作 + “减”动作 - “乘”动作 x “除”动作 ?;;运算式的组合-抽象与构造 ---程序构造示例I-计算对象的定义-构造与计算 ;运算式的组合-抽象与构造---程序构造示例 (1)运算组合式?;(+ 100 205) ;;(define height 2) ;(define pi 3.14159) ;运算式的组合-抽象与构造 ---程序构造示例II-运算符的定义-构造-与计算;(define (square x) (* x x)) ;名字的使用;(define (NewProc a) (SumOfSquare (+ a 1) (* a 2))) ;(NewProc (+ 3 1))的两种计算过程示意;(NewProc (+ 3 1))的两种计算过程示意;运算式的组合-抽象与构造 ---程序构造示例III-条件组合式的构造及总结;(cond ( p1 e1) ( p2 e2) ... ( pn en) ) ;问题1：用前缀表示法书写下述表达式 ;;;递归的概念;26;27;28;29;30;递归是一种表达相似性对象及动作的无限性构造的方法。 递归基础：定义、构造和计算的起点，直接给出； 递归步骤：由前n项或第n项定义第n+1项；由低阶f(k)且kn，来构造高阶f(n+1);;原始递归函数-复合与递归 ;34;35;36;;;;两种不同的递归函数---递归与迭代 ;41;42;43;44;;运用递归与迭代;运用递归和迭代 (1)运用递归进行无限自相似性对象的定义?;示例：“某人祖先”的递归定义 ;示例：简单命题逻辑的形式化递归定义 ;示例：树的形式化递归定义 ;;;;;递归与迭代程序的执行;;;n1;(define (fib n) ( cond ((= n 0) 0) ((= n 1) 1) (( n 1) (+ (fib (- n 1)) (fib (- n 2)))) ));;;具有无限的自相似性步骤的表达，循环-替代-递推—迭代;(define (fib n) ( fib-iter 1 0 n) ) (define (fib-iter a b count) ( cond ((= count 0) b) (( count 0) ( fib-iter (+ a b) a (- count 1) )))) ;递归是计算技术的典型特征，是以有限的表达方式来表达无限对象实例或无限计算步骤的一种经典的计算思维 递归覆盖了重复、迭代和递归，递归是最典型的构造手段 递归函数是可计算函数的精确的数学描述---计算理论的重要研究内容； (后面将介绍的)图灵机本质上也是递归：图灵可计算函数与递归函数等价，凡可计算的函数都是一般递归函数---丘奇-图灵命题---计算理论的重要研究内容；;;