《6.3 递归子例程电子课件 计算机系统基础：C语言视角（RISC-V版）.ppt》由会员分享，可在线阅读，更多相关《6.3 递归子例程电子课件 计算机系统基础：C语言视角（RISC-V版）.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、6.3 递归子例程电子课件 计算机系统基础：C语言视角（RISC-V版）递归示例：示例：计算计算 S Sn n递归方程递归方程Sn=Sn-1+n,n 2初始条件初始条件S1=1n=4n=4 S4=S3+4 =S2+3+4 =S1+2+3+4 =1+2+3+4将将n n的值赋值给的值赋值给x10 x10，调用，调用SnSn子例程，计算结果子例程，计算结果在在x11x11中中n=3n=301.data02.align203SaveReg:.word004#05.text06.align207.globlmain08main:addix10,x0,3#n=309jalx1,Sn#callSn0Aje
2、nd0B#递归递归子例程子例程 S Sn n0C Sn:0C Sn:lalax5,SaveRegx5,SaveReg0D 0D swswx1,0(x5)x1,0(x5)#caller-save#caller-save0E 0E addiaddix6,x0,1x6,x0,10F 0F beqbeqx10,x6,exit1x10,x6,exit1#n=1?#n=1?1010addiaddix10,x10,-1x10,x10,-1#n-1#n-11111jaljalx1,Snx1,Sn#调用调用S(n-1)S(n-1)1212addiaddix10,x10,1x10,x10,1#n#n13 13 a
3、ddaddx11,x11,x10 x11,x11,x10#S(n)=S(n-1)+n#S(n)=S(n-1)+n1414j jexit2exit215 exit1:15 exit1:addiaddix11,x0,1x11,x0,1#S(1)=1#S(1)=116 exit2:16 exit2:lalax5,SaveRegx5,SaveReg1717lwlwx1,0(x5)x1,0(x5)1818retret递归子例程：调用它本身的子例程递归子例程：调用它本身的子例程跟踪指令序列执行过程跟踪指令序列执行过程01.data02.align203 SaveReg:.word004#05.text06
4、.align207.globlmain08 main:addix10,x0,3#n=309jalx1,Sn#callSn.0C Sn:lax5,SaveReg0D swx1,0(x5)#caller-save0E addix6,x0,10F beqx10,x6,exit1#n=1?10addix10,x10,-1#n-111jalx1,Sn#调用调用S(n-1).0C Sn:lax5,SaveReg0D swx1,0(x5)#caller-save0E addix6,x0,10F beqx10,x6,exit1#n=1?10addix10,x10,-1#n-111jalx1,Sn#调用调用S(
5、n-1).0C Sn:lax5,SaveReg0D swx1,0(x5)#caller-save0E addix6,x0,10F beqx10,x6,exit1#n=1?10addix10,x10,-1#n-111jalx1,Sn#调用调用S(n-1)12addix10,x10,1#n13 addx11,x11,x10#S(n)=S(n-1)+n14jexit215 exit1:addix11,x0,1#S(1)=1.11jalx1,Sn#调用调用S(n-1)12addix10,x10,1#n13 addx11,x11,x10#S(n)=S(n-1)+n14jexit215 exit1:add
6、ix11,x0,1#S(1)=116 exit2:lax5,SaveReg17lwx1,0(x5)18ret.11jalx1,Sn#调用调用S(n-1)12addix10,x10,1#n13 addx11,x11,x10#S(n)=S(n-1)+n14jexit215 exit1:addix11,x0,1#S(1)=116 exit2:lax5,SaveReg17lwx1,0(x5)18ret无无限限循循环环：执执行行18行行的的ret指指令令，此此时时x1的的值值是是x0001 0028，返返回回到到12行行.注注意意，在在正正确确情情况况下下，此此时时已已经经计计算算结结束束，得得到到S3
7、的的结果，结果，应该返回应该返回0A行行“栈栈”机制机制造成错误的原因造成错误的原因递归调用子例程时，保存递归调用子例程时，保存返回地址返回地址x1x1的的指令将前指令将前一次保存的值覆盖了一次保存的值覆盖了如何解决？如何解决？答案答案采用采用“栈栈”机制机制栈栈 一种抽象数据类型一种抽象数据类型栈是一栈是一种种存储存储结构结构栈的概念栈的概念与实现无关与实现无关后进先出后进先出 (Last In,First Out)(Last In,First Out)，LIFOLIFO抽象数据类型抽象数据类型存储机制，由对它执行的操作所定义，而不是实存储机制，由对它执行的操作所定义，而不是实现它的方式现它
8、的方式栈栈 示例示例洗盘子洗盘子每洗净一个盘子，就放到另一个已经洗好的盘子每洗净一个盘子，就放到另一个已经洗好的盘子上面；上面；取盘子时，则是从这摞盘子中一个接一个向下拿。取盘子时，则是从这摞盘子中一个接一个向下拿。后进先出后进先出最后摆放上去的盘子是最先要拿走的最后摆放上去的盘子是最先要拿走的PUSH/POPPUSH/POP压栈压栈（pushpush）把一个元素插入栈把一个元素插入栈出栈出栈（poppop）移出一个元素移出一个元素在在内存内存中实现栈中实现栈由一组存储单元由一组存储单元和被称为和被称为“栈指栈指针针”的机制组成的机制组成栈指针栈指针寄存器寄存器x2x2指向指向栈的栈顶栈的栈顶
9、最后压入的元最后压入的元素的存储单元素的存储单元地址地址PUSHPUSHpushpush:addiaddix2,x2,-4x2,x2,-4 swswx9,0(x2)x9,0(x2)将保存在将保存在 x9中的数中的数值压值压入入栈栈POPPOPpoppop:lwlwx9,0(x2)x9,0(x2)addiaddix2,x2,4x2,x2,4注意：注意：数数值值-3仍然保存在仍然保存在0 xBFFF FFE4到到0 xBFFF FFE7这这一段存一段存储单储单元之中元之中栈协议栈协议“栈协议栈协议”，控制访问规则控制访问规则“栈栈”要求要求：通过执行通过执行PUSHPUSH指令序列实现压栈指令序列
10、实现压栈通过执行通过执行POPPOP指令序列实现出栈指令序列实现出栈后进先出后进先出pushpush:addiaddix2,x2,-4x2,x2,-4 swswx9,0(x2)x9,0(x2)poppop:lwlwx9,0(x2)x9,0(x2)addiaddix2,x2,4x2,x2,4采用栈机制的采用栈机制的SnSn0101lui x2,0 xc0000lui x2,0 xc00000202addi x2,x2,-16addi x2,x2,-16#x2=0 xBFFF FFF0#x2=0 xBFFF FFF00303addi x10,x0,3addi x10,x0,3#n=3#n=3040
11、4jal x1,Snjal x1,Sn#call Sn#call Sn0505j endj end06 06#07 Sn:07 Sn:addiaddix2,x2,-4x2,x2,-4#push x1#push x10808swswx1,0(x2)x1,0(x2)0909addiaddix6,x0,1x6,x0,10A0Abeqbeqx10,x6,exit1x10,x6,exit1#n=1?#n=1?0B0Baddiaddix10,x10,-1x10,x10,-1#n-1#n-10C0Cjaljalx1,Snx1,Sn#S(n-1)#S(n-1)0D0Daddiaddix10,x10,1x10,
12、x10,1#n#n0E 0E addaddx11,x11,x10 x11,x11,x10#S(n-1)+n#S(n-1)+n，S(n)S(n)的返回值的返回值0 0F Fj jexit2exit210 exit1:10 exit1:addiaddix11,x0,1x11,x0,1#x11#x11，S(1)S(1)的返回值的返回值11 11 exit2:exit2:lwlwx1,0(x2)x1,0(x2)#pop x1#pop x11212addiaddix2,x2,4x2,x2,41313retret跟踪指令序列执行过程跟踪指令序列执行过程0101lui x2,0 xc0000lui x2,0
13、 xc00000202addi x2,x2,-16addi x2,x2,-16#x2=0 xBFFF FFF0#x2=0 xBFFF FFF00303addi x10,x0,3addi x10,x0,3#n=3#n=30404jal x1,Snjal x1,Sn#call Sn#call Sn0505j endj end06 06#07 Sn:07 Sn:addiaddix2,x2,-4x2,x2,-4#push x1#push x10808swswx1,0(x2)x1,0(x2)0909addiaddix6,x0,1x6,x0,10A0Abeqbeqx10,x6,exit1x10,x6,ex
14、it1#n=1?#n=1?0B0Baddiaddix10,x10,-1x10,x10,-1#n-1#n-10C0Cjaljalx1,Snx1,Sn#S(n-1)#S(n-1).07 Sn:07 Sn:addiaddix2,x2,-4x2,x2,-4#push x1#push x10808swswx1,0(x2)x1,0(x2)0909addiaddix6,x0,1x6,x0,10A0Abeqbeqx10,x6,exit1x10,x6,exit1#n=1?#n=1?0B0Baddiaddix10,x10,-1x10,x10,-1#n-1#n-10C0Cjaljalx1,Snx1,Sn#S(n-1
15、)#S(n-1).07 Sn:07 Sn:addiaddix2,x2,-4x2,x2,-4#push x1#push x10808swswx1,0(x2)x1,0(x2)0909addiaddix6,x0,1x6,x0,10A0Abeqbeqx10,x6,exit1x10,x6,exit1#n=1?#n=1?0B0Baddiaddix10,x10,-1x10,x10,-1#n-1#n-10C0Cjaljalx1,Snx1,Sn#S(n-1)#S(n-1)0D0Daddiaddix10,x10,1x10,x10,1#n#n0E 0E addaddx11,x11,x10 x11,x11,x10#S
16、(n-1)+n#S(n-1)+n，S(n)S(n)的返回值的返回值0 0F Fj jexit2exit210 exit1:10 exit1:addiaddix11,x0,1x11,x0,1#x11#x11，S(1)S(1)的返回值的返回值.0C0Cjaljalx1,Snx1,Sn#S(n-1)#S(n-1)0D0Daddiaddix10,x10,1x10,x10,1#n#n0E 0E addaddx11,x11,x10 x11,x11,x10#S(n-1)+n#S(n-1)+n，S(n)S(n)的返回值的返回值0 0F Fj jexit2exit210 exit1:10 exit1:addia
17、ddix11,x0,1x11,x0,1#x11#x11，S(1)S(1)的返回值的返回值11 11 exit2:exit2:lwlwx1,0(x2)x1,0(x2)#pop x1#pop x11212addiaddix2,x2,4x2,x2,41313retret0C0Cjaljalx1,Snx1,Sn#S(n-1)#S(n-1)0D0Daddiaddix10,x10,1x10,x10,1#n#n0E 0E addaddx11,x11,x10 x11,x11,x10#S(n-1)+n#S(n-1)+n，S(n)S(n)的返回值的返回值0 0F Fj jexit2exit210 exit1:10 exit1:addiaddix11,x0,1x11,x0,1#x11#x11，S(1)S(1)的返回值的返回值11 11 exit2:exit2:lwlwx1,0(x2)x1,0(x2)#pop x1#pop x11212addiaddix2,x2,4x2,x2,41313retret