递归过程与递归工作栈 递归过程在实现时,需要自己调用自己。 层层向下递归,退出时的次序正好相反: 递归调用 n!=(-1)=(n-2)!→■→1!今0!=1 返回次序 主程序第一次调用递归过程为外部调用 递归过程每次递归调用自己为内部调用 。它们返回调用它的过程的地址不同
递归过程与递归工作栈 ◼ 递归过程在实现时，需要自己调用自己。 ◼ 层层向下递归，退出时的次序正好相反： 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序 ◼ 主程序第一次调用递归过程为外部调用； ◼ 递归过程每次递归调用自己为内部调用。 ◼ 它们返回调用它的过程的地址不同
递归工作栈 每一次递归调用时,需要为过程中使用 的参数、局部变量等另外分配存储空间。 每层递归调用需分配的空间形成递归工 作记录,按后进先出的栈组织。 活动局部变量 递归 记录{返回地址工作记景 框架参数
递归工作栈 ◼ 每一次递归调用时，需要为过程中使用 的参数、局部变量等另外分配存储空间。 ◼ 每层递归调用需分配的空间形成递归工 作记录，按后进先出的栈组织。 局部变量 返回地址 参 数 活动 记录 框架 递归 工作记录
函数递归时的活动记录 调用块 ●●●●●●●●●。0●0●●●● <下一条指令> 数A十 Function(参数表>) <return> 返回地址(下一条指令)局部变量参数
函数递归时的活动记录 ………………. <下一条指令> Function(<参数表>) ………………. <return> 调用块 函数块 返回地址(下一条指令) 局部变量 参数
long Factorial long n)( int temp, if (n==0)return 1; else temp =n* Factorial(n-1); RetLoc2 return temp: void main (i int ns n= Factorial (4) Retloc l
long Factorial ( long n ) { int temp; if ( n == 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; } void main ( ) { int n; n = Factorial (4); RetLoc1 }
计算Fac时活动记录的内容 参数返回地址返回时的指令 4 RetLocl RetLocl return4*6/返回24 递 归3 RetLoc2 Retloc2rem3+2/返回6 调 用2Relo2 Retloc?2 return2*1/返回2 序 列 1 Retloc2 Retloc2 return1*1/返回1 0 Retloc2 Retloc2 return1/返回1
计算Fact时活动记录的内容 递 归 调 用 序 列 0 RetLoc2 1 RetLoc2 2 RetLoc2 3 RetLoc2 4 RetLoc1 参数 返回地址 返回时的指令 RetLoc1 return 4*6 //返回24 RetLoc2 return 3*2 //返回6 RetLoc2 return 1 //返回1 RetLoc2 return 1*1 //返回1 RetLoc2 return 2*1 //返回2