在递归阶乘程序中，当函数返回时堆栈帧如何维护? [英] In Recursion factorial program when a function is returning how stack FRAMES are maintained?

问题描述

例如:函数实现:

 facto(x){
     if(x==1){ 
             return 1;
      }
      else{ 
           return x*facto(x-1); 
     }

用更简单的方式来获取堆栈 -->

in more simple way lets take a stack -->

        returns
 |2(1)|---->    2(1) evaluates to 2
 |3(2)|---->    3(2)<______________| evaluates to 6
 |4(3)|---->    4(6)<______________| evaluates to 24
 |5(4)|---->    5*(24)<____________| evaluates to 120
 ------         finally back to main...

当一个函数以相反的方式返回时，它永远不知道它背后到底是什么?堆栈中存储了激活记录，但它们如何相互了解谁被弹出，谁在顶部?堆栈如何跟踪函数中的所有变量被执行?除此之外，它如何跟踪执行的代码(堆栈指针)?当从函数调用返回结果时函数将填充占位符.通过使用堆栈指针但是它如何知道在哪里继续执行代码呢?这些是我知道堆栈如何工作的基础知识，但对于递归我不知道了解它究竟是如何工作的??

when a function returns in reverse manner it never knows what exactly is behind it? The stack have activation records stored inside it but how they know about each other who is popped and who is on top? How the stack keeps track of all variables within the function being executed? Besides this, how it keeps track of what code is executed (stackpointer)? When returning from a function call the result of that function will be filled in a placeholder. By using the stackpointer but how it knows where to continue executing code? These are the basics of how the stack works I know but for recursion I don't understand how it exactly works??

推荐答案

当函数返回时，它的堆栈帧被丢弃(即完整的本地状态被弹出堆栈).

When a function returns its stack frame is discarded (i.e the complete local state is pop-ed out of the stack).

细节取决于处理器架构和语言.

The details depend on the processor architecture and language.

检查 x86 处理器的 C 调用约定:http://en.wikipedia.org/wiki/X86_calling_conventions, http://en.wikibooks.org/wiki/X86_Disassembly/Functions_and_Stack_Frames 并搜索 Paul A. Carter 的PC 汇编语言"(它有点过时，但它对 ia32 架构的 C 和 Pascal 调用约定有很好的解释).

Check the C calling conventions for x86 processors: http://en.wikipedia.org/wiki/X86_calling_conventions, http://en.wikibooks.org/wiki/X86_Disassembly/Functions_and_Stack_Frames and search for "PC Assembly Language" by Paul A. Carter (its a bit outdated but it has a good explanation of C and Pascal calling conventions for the ia32 architecture).

在 x86 处理器中的 C 中:

In C in x86 processors:

一个.调用函数将被调用函数的参数以相反的顺序压入堆栈，然后将指针压入返回地址.

a. The calling function pushes the parameters of the called function to the stack in reverse order and then it pushes the pointer to the return address.

push -6
push 2
call add     # pushes `end:` address an then jumps to `add:` (add(2, -6))
end:
# ...

B.然后被调用函数压入栈底(ia32中的ebp寄存器)(用于在调用者函数中引用局部变量).

b. Then the called function pushes the base of the stack (the ebp register in ia32) (it is used to reference local variables in the caller function).

add:
push ebp

c.被调用的函数将 ebp 设置为当前堆栈指针(这个 ebp 将是访问当前函数实例的局部变量和参数的引用).

c. The called function sets ebp to the current stack pointer (this ebp will be the reference to access the local variables and parameters of the current function instance).

add:
# ...
mov ebp, esp

d.被调用的函数在堆栈中为局部(自动)变量保留空间，减去变量的大小到堆栈指针.

d. The called function reserves space in the stack for the local (automatic) variables subtracting the size of the variables to the stack pointer.

add:
# ...
sub esp, 4     # Reserves 4 bytes for a variable

e.在被调用函数结束时，它将堆栈指针设置为 ebp(即释放其局部变量)，恢复调用者函数的 ebp 寄存器并返回到返回地址(之前由调用者压入).

e. At the end of the called function it sets the stack pointer to be ebp (i.e frees its local variables), restores the ebp register of the caller function and returns to the return address (previously pushed by the caller).

add:
# ...
mov esp, ebp  # frees local variables
pop ebp       # restores old ebp
ret           # pops `end:` and jumps there

f.最后，调用者将被调用函数的参数使用的空间添加到堆栈指针中(即释放参数使用的空间).

f. Finally the caller adds to the stack pointer the space used by the parameters of the called function (i.e frees the space used by the arguments).

# ...
end:
add esp, 8

返回值(除非它们大于寄存器)在 eax 寄存器中返回.

Return values (unless they are bigger than the register) are returned in the eax register.

这篇关于在递归阶乘程序中，当函数返回时堆栈帧如何维护?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！