6.3 递归子例程电子课件

递归示例：计算Sn递归方程Sn=Sn-1+n,n

2初始条件S1=1n=4 S4

=S3

+4=S2

+3+4=S1

+2+3+4=1+2+3+4将n的值赋值给x10，调用Sn子例程，计算结果在x11中n=301 .data02 .align 203 SaveReg: .word 004 #05 .text06 .align 207 .globl main08 main: addi x10,x0,3 #n=309 jal x1,Sn

#call Sn0A j end0B #递归子例程

Sn0CSn: la x5,SaveReg0D sw x1,0(x5) #caller-save0E addi x6,x0,10F beq x10,x6,exit1 #n==1?10 addi x10,x10,-1 #n-111 jal x1,Sn

#调用S(n-1)12 addi x10,x10,1 #n13 add x11,x11,x10 #S(n)=S(n-1)+n14 j exit215exit1: addi x11,x0,1 #S(1)=116exit2: la x5,SaveReg17 lw x1,0(x5)18 ret递归子例程：调用它本身的子例程跟踪指令序列执行过程01 .data02 .align 203 SaveReg: .word 004 #05 .text06 .align 207 .globl main08 main: addi x10,x0,3 #n=309 jal x1,Sn

#call Sn............0CSn: la x5,SaveReg0D sw x1,0(x5)

#caller-save0E addi x6,x0,10F beq x10,x6,exit1 #n==1?10 addi x10,x10,-1 #n-111 jal x1,Sn

#调用S(n-1)……......0CSn: la x5,SaveReg0D sw x1,0(x5)

#caller-save0E addi x6,x0,10F beq x10,x6,exit1 #n==1?10 addi x10,x10,-1 #n-111 jal x1,Sn

#调用S(n-1)……......0CSn: la x5,SaveReg0D sw x1,0(x5)

#caller-save0E addi x6,x0,10F beq x10,x6,exit1 #n==1?10 addi x10,x10,-1 #n-111 jal x1,Sn

#调用S(n-1)12 addi x10,x10,1 #n13 add x11,x11,x10 #S(n)=S(n-1)+n14 j exit215exit1: addi x11,x0,1

#S(1)=1......11 jal x1,Sn

#调用S(n-1)12 addi x10,x10,1

#n13 add x11,x11,x10

#S(n)=S(n-1)+n14 j exit215exit1: addi x11,x0,1 #S(1)=116exit2: la x5,SaveReg17 lw x1,0(x5)18 ret......11 jal x1,Sn

#调用S(n-1)12 addi x10,x10,1

#n13 add x11,x11,x10

#S(n)=S(n-1)+n14 j exit215exit1: addi x11,x0,1 #S(1)=116exit2: la x5,SaveReg17 lw x1,0(x5)18 ret无限循环：执行18行的ret指令，此时x1的值是x00010028，返回到12行......注意，在正确情况下，此时已经计算结束，得到S3的结果，应该返回0A行“栈”机制造成错误的原因递归调用子例程时，保存返回地址x1的指令将前一次保存的值覆盖了如何解决？答案采用“栈”机制栈

——一种抽象数据类型栈是一种存储结构栈的概念与实现无关后进先出

(LastIn,FirstOut)，LIFO抽象数据类型存储机制，由对它执行的操作所定义，而不是实现它的方式栈

——示例洗盘子每洗净一个盘子，就放到另一个已经洗好的盘子上面；取盘子时，则是从这摞盘子中一个接一个向下拿。后进先出最后摆放上去的盘子是最先要拿走的PUSH/POP压栈（push）把一个元素插入栈出栈（pop）移出一个元素在内存中实现栈由一组存储单元和被称为“栈指针”的机制组成栈指针寄存器x2指向栈的栈顶最后压入的元素的存储单元地址PUSHpush: addi x2,x2,-4 sw x9,0(x2)将保存在x9中的数值压入栈POPpop: lw x9,0(x2) addi x2,x2,4注意：数值-3仍然保存在0xBFFFFFE4到0xBFFFFFE7这一段存储单元之中栈协议“栈协议”，控制访问规则“栈”要求：通过执行PUSH指令序列实现压栈通过执行POP指令序列实现出栈后进先出push: addi x2,x2,-4 sw x9,0(x2)pop: lw x9,0(x2) addi x2,x2,4采用栈机制的Sn01 luix2,0xc000002 addix2,x2,-16 #x2=0xBFFFFFF003 addix10,x0,3 #n=304 jalx1,Sn #callSn05 jend06#

07Sn: addi x2,x2,-4 #pushx108 sw x1,0(x2) 09 addi x6,x0,10A beq x10,x6,exit1 #n==1?0B addi x10,x10,-1 #n-10C jal x1,Sn

#S(n-1)0D addi x10,x10,1 #n0E add x11,x11,x10#S(n-1)+n，S(n)的返回值0F j exit210exit1: addi x11,x0,1 #x11，S(1)的返回值11exit2: lw x1,0(x2) #popx112 addi x2,x2,413 ret跟踪指令序列执行过程01 luix2,0xc000002 addix2,x2,-16 #x2=0xBFFFFFF003 addix10,x0,3 #n=304 jalx1,Sn

#callSn05 jend06#

07Sn: addi x2,x2,-4

#pushx108 sw x1,0(x2)

09 addi x6,x0,10A beq x10,x6,exit1 #n==1?0B addi x10,x10,-1

#n-10C jal x1,Sn

#S(n-1)......07Sn: addi x2,x2,-4

#pushx108 sw x1,0(x2)

09 addi x6,x0,10A beq x10,x6,exit1 #n==1?0B addi x10,x10,-1

#n-10C jal x1,Sn

#S(n-1)......07Sn: addi x2,x2,-4

#pushx108 sw x1,0(x2)

09 addi x6,x0,10A beq x10,x6,exit1 #n==1?0B addi x10,x10,-1 #n-10C jal x1,Sn

#S(n-1)0D addi x10,x10,1 #n0E add x11,x11,x10 #S(n-1)+n，S(n)的返回值0F j exit210exit1: addi x11,x0,1

#x11，S(1)的返回值......0C jal x1,Sn

#S(n-1)0D addi x10,x10,1

#n0E add x11,x11,x10

#S(n-1)+n，S(n)的返回值0F j exit210exit1: addi x11,x0,1 #x11，S(1)的返回值11exit2: lw x1,0(x2)

#popx112 addi x2,x2,413 ret0C j