此递归函数如何工作 [英] how does this recursive function works

问题描述

我是编程的新手，我开始读一本有关它的书以了解基础知识.我不明白以下汇编代码的工作原理:它计算数字的阶乘.我已经在我可以理解的说明中添加了评论-显然我遗漏了一些东西.

I'm new to programming, and I'm starting to read a book about it to understand the fundamentals. I couldn't understand how the following assembly code works: it calculates the factorial of a number. I have added comments to the instructions that I can understand - clearly I'm missing something.

    .section .data
    .section .text
    .globl _start
    .globl factorial

_start:

    pushl $4             
    call factorial         
    popl %ebx              
    movl %eax, %ebx        
    movl $1, %eax          
    int $0x80

factorial:

    pushl %ebp              # push the base pointer
    movl %esp, %ebp         # copy the stack pointer to the base pointer
    movl 8(%ebp), %eax      # move the value 4 to %eax
    cmpl $1, %eax           # compare it to 1
    je end_factorial        # jump to end_factorial if it's equal
    decl %eax               # else decrease the value by 1
    pushl %eax              # push the decreased value in the stack
    call factorial          # this means that it should start again (?)

    popl %ebx               # that's the part that i don't understand
    incl %ebx               # when are these lines excuted? since it
    imul %ebx, %eax         # keeps starting from the top, until the value
                            # of %eax is 1 then, it jumps to end_factorial

end_factorial:

    movl %ebp, %esp
    popl %ebp
    ret`

推荐答案

不要在上下文中进行注释，而应将注释放在上下文中.

Don't comment acontextually, rather put the comments in context.

不要将将值4移动到％eax ，而是找到含义:将 n 移动到eax .
不要跟踪寄存器值，而要跟踪变量:否则将值减小1 更好，因为 eax = n-1

Don't write move the value 4 to %eax, instead find the meaning: move n to eax.
Don't keep track of the register values, keep track of the variables: else decrease the value by 1 is better as eax = n - 1

如果您再次尝试对该程序进行注释，您应该会看到类似下面的内容.

If you try commenting the program again you should arrive at something like the below.

.section .data
.section .text

.globl _start                 
.globl factorial

_start:

    pushl $4             
    call factorial          # eax = 4! 
    popl %ebx               # Remove the parameter from the stack       

    movl %eax, %ebx
    movl $1, %eax          
    int $0x80               # sys_exit(4!)

factorial:

    pushl %ebp
    movl %esp, %ebp         # Prolog

    movl 8(%ebp), %eax      # eax = n

    cmpl $1, %eax           # n == 1?
    je end_factorial        # If yes, since 1! = 1, just return

    decl %eax               # eax = n - 1

    pushl %eax              
    call factorial          # eax = (n - 1)!

    popl %ebx               # ebx = (n - 1)
    incl %ebx               # ebx = n
    imul %ebx, %eax         # eax = n * (n - 1)! = n!

end_factorial:

    movl %ebp, %esp         # Prolog
    popl %ebp
    ret

通过这些注释，现在可以公开该功能的工作-这是一个非常标准的，无尾递归的阶乘实现.

With these comments the function working is now unveiled - it is a pretty standard, non tail recursive, factorial implementation.

int fact(int n)
{
   if (n == 1)
      return 1;

   return n * fact(n-1);
}

有关执行流程的问题，特别是递归关闭后执行什么代码，可以在稍微使用铅笔和橡胶后回答.
最后，您会发现要查找的重要部分是终止条件(终止情况)-它是不会涉及任何递归调用的输入.
在此示例中， n = 1 .

Questions about the execution flow, particularly what code is executed after the recursion closes, can be answered after a bit of use of a pencil and a rubber.
In the end you'll see that the important part to look for is the termination condition (termination case) - it is the input that won't span any more recursive call.
In this example is n = 1.

扎实理解功能的另一个必要条件是功能的实际工作方式-每次调用都是一个唯一的实例，并且在函数返回后，调用者的状态会以调用者的状态继续执行(恢复了调用者的调用).
从而创建一个(抽象的)保存/恢复状态的堆栈.

Another pillar necessary for a solid understanding of the function is how functions actually work - the fact that each invocation is an unique instance and that after a function return execution continues at the caller with the caller's state (the caller invocation is restored).
Thereby creating a (abstract) stack of saved/restored states.

该实现的唯一特殊方面是用于清除函数参数堆栈的指令.
如果上面的句子让您不满意，建议您阅读调用约定.
通常使用addl $4, %esp，在代码中使用popl %ebx代替-虽然在factorial主体中是有意义的，因为在递归调用之后再次需要n，但在功能.

The only peculiar aspect of that implementation is the instruction used to clean the stack of the function parameter.
If the sentence above throw you off, I advise to read about calling conventions.
Usually an addl $4, %esp is used, in the code a popl %ebx is used instead - while it makes sense in the factorial body since n is necessary again after the recursive call, its use is quite strange in the _start function.

这篇关于此递归函数如何工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！