计算机科学导论-计算思维程序实践 课件 第5、6讲-从两种不同的递归函数看规模化计算的规则表达与执行-递归与迭代、从学生宿舍管理看存储器-基于编码的管理思维

第5讲从两种不同的递归函数看规模化计算的规则表达与执行--递归与迭代哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣2递归的概念递归的典型视觉形式---自相似性事物的无限重复性构造递归是表达相似性对象及动作的无限性重复性构造的方法。递归基础：定义、构造和计算的起点，直接给出。即h(0)。递归步骤：由第n项或前n项定义第n+1项。即:h(n+1)

=g(h(n),n)，g是需要明确给出的，以说明h(n+1)怎样由h(n)和n构造出来。递归的概念什么是递归？4(1)某人的双亲(父母)是他的祖先（递归基础）---h(1)直接给出(2)某人祖先的双亲(父母)同样是某人的祖先（递归步骤/公式）---h(n+1)=g(h(n),n)

---n:第几代；h(n)是第几代祖先；g是h(n+1)与h(n)和n的关系曾祖父曾祖母(祖父的)父(祖父的)母祖父祖母(父的)父(父的)母父母外祖父外祖母(母的)父(母的)母某人h(1)h(2)h(3)h(n)h(0)h(n+1)用递归进行定义怎样递归？【示例】怎样定义你的祖先?递归的理解比较难递归思维是计算机最重要的特征想学计算机就要理解递归思维5Fibonacci数列，无穷数列1，1，2，3，5，8，13，21，34，55，……，

F(0)=1; F(1)=1; F(2)=F(1)+F(0)=2; F(3)=F(2)+F(1)=3; F(4)=F(3)+F(2)=3+2=5;……递归定义递推计算/迭代计算/迭代执行体验两种不同的递归函数一种类型的递归函数：定义是递归的,但执行可以是递归的也可以是迭代的计算规则的表达—告诉执行者要递归计算执行者要一步一步地完成计算获得结果6A(1,n)=A(0,A(1,n-1))=A(0.<…代入前式计算过程>)=A(0,n+1)=n+2。A(2,1)=A(1，A(2，0))

--A(2,1)按m,n>0公式代入 =A(1，A(1，1))

--A(2,0)按n=0公式代入 =A(1，A(0，A(1，0)))

--A(1,1)按m,n>0公式代入 =A(1，A(0，A(0，1)))

--A(1,0)按n=0公式代入 =A(1，A(0，2))

--A(0,1)按m=0公式代入 =A(1，3)

--A(0,2)按m=0公式代入 =A(0，A(1，2))

--A(1,3)按m,n>0公式代入 =A(0，A(0，A(1，1)))

--A(1,2)按m,n>0公式代入 =A(0，A(0，A(0，A(1，0))))

--A(1,1)按m,n>0公式代入 =A(0，A(0，A(0，A(0,1)))

--A(1,0)按n=0公式代入 =A(0，A(0，A(0，2)))

--A(0,1)按m=0公式代入 =A(0，A(0，3))=A(0，4)=5。--依次按m=0公式代入体验两种不同的递归函数另一种类型的递归函数：定义是递归的,但执行也是递归的（用迭代不容易完成）函数本身是递归的，函数的变量也是递归的

递归定义递归计算/递归执行由后向前代入，再由前向后计算阿克曼递归函数

计算规则的表达—告诉执行者要递归计算执行者要一步一步地完成计算获得结果h(0)h(n+1)h(0)h(n+1)寻找路径沿路径计算沿一致路径计算h(0)h(n+1)可能计算路径并不同迭代/递推递归通常，只能由函数结构实现在前次结果基础上进行计算可采用循环结构实现重复性无限性构造的思维--递归与迭代?(6)两种不同的递归函数--递归与递推(迭代)的差别?两种不同的递归函数：递归与迭代递归与迭代的差异longintFact(intn){longintx; If(n>1){x=Fact(n-1);/*递归调用*/returnn*x;}elsereturn1;/*递归基础*/}n>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nFact(n)

递归程序的构造与执行运用递归进行程序构造：函数结构，自身调用自身，高阶调用低阶【示例】求n!的算法或程序--用递归方法构造：函数调用n>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nFact(4)4返回4!=24Fact(3)返回3!=624Fact(2)返回2!=2Fact(1)返回1!=13622114

63

22

1126递归程序的构造与执行递归程序的执行过程：利用【堆栈】保存待计算的数据123456Fact(4)的程序断点

Fact(3)的程序断点Fact(4)的程序断点

Fact(2)的程序断点Fact(3)的程序断点Fact(4)的程序断点

堆栈：后进先出longintFact(intn){intcounter；

longproduct=1;forcounter=1tonstep1{product=product*counter；}/*迭代*/returnproduct;}

CounterProduct初始值1

Fact(5)的执行过程【示例】求n!的算法或程序--用迭代方法构造：循环-替代-递推迭代程序的构造与执行迭代程序的执行过程?循环第1次 1 1循环第2次

2 2循环第3次

3 6循环第4次

4

24循环第5次

5

120退出循环

6

120递归是表达相似性对象及动作的无限性重复性构造的方法。递归基础：定义、构造和计算的起点，直接给出。即h(0)。递归步骤：由第n项或前n项定义第n+1项的一个或一组公式。递归是一种关于抽象的表达方法---用递归定义无限的相似事物递归是一种算法或程序的构造技术---自身调用自身，高阶调用低阶，构造无限的计算步骤递归是一种典型的计算/执行过程---由后向前代入，直至代入到递归基础，再由递归基础向后计算直至计算出最终结果，即由前向后计算数学上用递归定义，但算法上有些可由递归算法/程序实现，有些可由迭代算法/程序实现。迭代算法/程序的执行效率要远高于递归算法/程序，因此能用迭代实现的尽量不用递归。能用迭代算法实现的，都能用递归算法实现；而能用递归算法实现的，却未必都能用迭代算法实现。递归算法是用【函数】结构来表达的，而迭代算法是用【循环】结构来表达的。递归算法执行需要【堆栈】（一种后进先出的数据结构）予以支持。用递归定义用递归构造递归计算/执行递归与迭代小结第6讲从学生宿舍管理看存储器

—基于编码的管理思维哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣程序?程序自动执行?数据计算规则表示?自动存取?自动执行?计算机器回顾计算机器的基本思维存储器中央处理单元(CPU)0和1（比特）内存储器/主存储器【存储器】能够按地址读或写每一个存储单元的部件。【存储单元】一个存储单元可以保存一个m位的数据，通常记为Dm-1…D0。【地址】是一个n位的0/1编码，每一个编码指向一个存储单元，通常记为An-1…A0。存储器的基本概念什么是存储器？存储器宿舍楼存储单元房间存储位(存0或存1)床位(住人/不住人)地址编码An-1…A0房间号单元控制线Wi房间钥匙输出缓冲器公共的走廊及大门………概念映射从存储器与宿舍楼的概念对比中，你能发现什么异同吗？存储器的基本概念对比宿舍楼，理解存储器的相关概念同一时刻只能有一个W有效（接通存储单元）存储单元(的内容)(存储单元的)地址地址空间存储字长存储容量地址编码n位：An-1…A0地址空间：

00000000…0000000000000000…00000001

……11111111…11111111存储字长m位：Dm-1…D0

每个存储单元都是m位存储容量=2n

mBit(位)

=2n

m/8Byte（字节)存储容量的单位：210为换算单位2n个存储单元DB、NB、BB、YB、ZB、EB、PB、TB、GB、MB、KB、Byte存储器的基本概念存储器的容量

存储器内部的实现示例当单元控制线W和数据线D间连接有二极管时，则存储的是1，否则，存储的是0。这是只读存储器（ROM，只能读出不能写入）示例。二极管ROM结构示例(2位地址控制4个存储单元,每个存储单元是4位0/1)一个存储单元自动存取：存储器的工作原理存储器是怎样存储0和1的?又是怎样控制存取的?二极管ROM结构示例(2位地址控制4个信息单元,每个信息单元是4位0/1码)111010110010111111000001010101自动存取：存储器的工作原理存储器是怎样存储0和1的?又是怎样控制存取的?

存储器内部的实现示例当单元控制线W和数据线D间连接有二极管时，则存储的是1，否则，存储的是0。这是只读存储器（ROM，只能读出不能写入）示例。当单元控制线W和数据线D间连接有二极管时，由单元控制线决定其是输出1或0，即：当单元控制线为1（高电压）时，则输出1（高电压），而当单元控制线为0（低电压）时，则输出0（低电压）。没有连接的，则不受单元控制线影响，始终输出0（低电压）。

W3,W2,W1,W0随着A1A0的值同时只能有一个为1（高电压）其它为0（低电压），即控制一个存储单元所有位的读写。尽管所有存储单元的第i位都连接到Di，但只有将读取存储单元的第i位对Di产生作用。Dj是数据线Ak是地址编码线Wi是单元控制线存储矩阵：一种【与或逻辑】阵列【地址编码线】与【单元控制线】有黑点则连接，无黑点则不连接。【单元控制线】与【数据线】有黑点则连接，无黑点不连接。高/低电压信号，即0,1，通过连接点相互传递。上半部是【与】阵列，下半部是【或】阵列。存储器实现的逻辑控制存储矩阵的逻辑控制关系Dj是数据线Ak是地址编码线Wi是单元控制线11001000W0=(NOTA0)AND(NOTA1)W1=A0AND(NOTA1)W2=(NOTA0)ANDA1W3=A0ANDA1译码器：将A1A0地址编码翻译到只有一条单元控制线Wi为1,其它为0。【与】阵列，表述了如何由A1A0的值产生W0,W1,W2,W3的值（只能有一条线为1），由横线向纵线传输信号—上半部。同一【单元控制线】上各连接点之间是

“与”关系。即只有各连接点都为1时，该单元控制线的信号为1，否则为0。存储器实现的逻辑控制存储矩阵的逻辑控制关系Dj是数据线Ak是地址编码线Wi是单元控制线11001000输出矩阵：将Wi为1的单元控制线控制的存储单元的值进行输出。【或】阵列，表述了如何由W3W2W1W0的值产生D3,D2,D1,D0的值。单元控制线与数据线之间有黑点连接的，表示存储的是1，其能否输出取决于单元控制线是1还是0。由纵线向横线传输信号—下半部。同一【数据线】上各连接点之间是

“或”关系。即各连接点只要有一个为1时，该数据线的信号为1，否则为0。D3=W0ORW2D2=W1ORW2ORW3D1=W1ORW2D0=W0ORW1ORW30101存储器实现的逻辑控制存储矩阵的逻辑控制关系每个房间8个人，16个房间D7D6…D0A3A2A1A04位房间号8个人-出与入楼控MA3A2A1A000000001…011110001001…11112568RAMI/O0I/O1I/O2I/O3I/O4I/O5I/O6I/O7A0A1A2A3A4A5A6A7R/WCS地址编码线8位（编码256个地址）数据线8位（即D7D6D5D4D3D2D1D0）控制存储单元的读或写当加高电压(1)时读出，当加低电压(0)时写入。芯片是否工作的控制。当加高电压(1)时不工作，当加低电压(0)时工作。168标准宿舍楼存储器容量不够怎么办？存储器芯片vs.标准宿舍楼每个房间8个人，16个房间D7D6…D0A3A2A1A04位房间号8个人-出与入楼控M168标准宿舍楼一个标准宿舍楼：16个房间，每个房间住8人

A3A2A1A0D7…D0住宿需求：64个大房间，每个大房间住16人？B5B4B3B2B1B0E15…E8E7…E0存储器容量不够怎么办？一个宿舍楼不够怎么办？住宿需求：64个大房间，每个大房间住16人？B5B4B3B2B1B0

E15…E8E7…E0解决方案第1步：2个标准宿舍楼对应相同地址B3B2B1B0的房间构成一个大房间，其中编号为E15…E8住上面的楼，而E7…E0住下面的楼，确保他们的地址A3A2A1A0在同一时刻是相同的，即同时进出。E7E6…E0E15E14…E8B3B2B1B0存储器容量不够怎么办？多个宿舍楼拼接在一起使用住宿需求：64个大房间，每个大房间住16人？B5B4B3B2B1B0

E15…E8E7…E0