汇编中的递归

Question

我需要有关刚开始学习的汇编代码的帮助。

.intel_syntax noprefix;
.text;
.globl main;

main:
    mov eax, 3;
    mov ebx, 0;
    push eax;
    push ebx;
    call f;
    add esp, 8;
    push eax;
    mov eax, offset message;
    push eax;
    call printf
    add esp,8;
    mov eax,0;
    ret;

f:
    mov eax, [esp+8];
    mov ebx, [esp+4];
    cmp eax,3;
    jge ety2;
    cmp eax,2;
    je ety1;
    cmp eax,0;
    je ety1;
    cmp eax,1;
    je ety3;
    ety3:
    mov eax,0;
    ret;

ety1:
    mov eax,1;
    ret;

ety2:
    xor ebx,ebx;
    dec eax;
    push eax;
    push ebx;
    call f;
    add esp,8;
    add ebx,[esp+4];
    add ebx,eax;
    mov eax,[esp+8];
    dec eax;
    dec eax;
    push eax;
    push ebx;
    call f;
    add esp,8;
    add ebx,[esp+4];
    add ebx,eax;
    add ebx,eax;
    mov eax,[esp+8];
    dec eax;
    dec eax;
    dec eax;
    push eax;
    push ebx;
    call f;
    add esp,8;
    add ebx,[esp+4];
    sub ebx,eax;
    mov eax,[esp+8];
    mov eax,ebx;
    ret;

.data;
message:
.asciz "Result=%i\n";
.att_syntax prefix;

在主函数中 'eax' 寄存器用作函数的 'n' 参数：

for n=0 or n=2 returns 1;
for n=1 returns 0;
for n>=3 returns f(n-1)+(2*f(n-2))-f(n-3);

所以对于 n=3 函数 returns 0, n=4 returns 2, n=5 returns 1, n=6 returns 5 e.t.c.

递归有很多问题，对于值 < 5 函数工作正常，但对于 6、7 e.t.c。 function returns 极高或极低（负）值。我已经为此工作了 +10 个小时，但我无法让它发挥作用属性。我究竟做错了什么？

需要使用"PUSH"和“[esp+4]”、"add esp,4;"等代码中已有的简单指令。程序在-m32命令参数下编译(gcc -Wall funcas.s -m32 -o test).

我用 C 写下了相同的代码来展示我想要实现的目标

#include <stdio.h>
#include <stdlib.h>

int funkcja(int n)
{
    if(n>=3)
    {
        return (funkcja(n-1)+(2*funkcja(n-2))-funkcja(n-3));
    }
    else
    {   
        if(n==2)return 1;
        if(n==1)return 0;
        if(n==0)return 1;
    }
    return -1;
}

int main()
{
    int a=6;
    printf("%d\n", funkcja(a));
    return 0;
}

Answer 1

问题在于代码不断累积所有结果。将 f 更改为仅使用一个参数。 Microsoft 类型汇编代码示例。在 f() 和 main() 中，n 都存储在堆栈中。

        .model  flat,c
;       ...
        .data
fmt     db      '%d',00ah,000h

        .code
        extern  printf:proc
        public  main

f       proc                    ;int f(int n)
        mov     eax, [esp+4]
        cmp     eax,3
        jge     f2
        cmp     eax,2
        je      f1
        cmp     eax,1
        je      f0
        cmp     eax,0
        je      f1
        mov     eax,-1
        ret

f0:     mov     eax,0
        ret

f1:     mov     eax,1
        ret

f2:     push    ebx             ;save ebx
        dec     eax             ;eax = n-1
        push    eax             ;[esp] = n-1
        call    f               ;eax = f(n-1)
        mov     ebx,eax         ;ebx = f(n-1)
        dec     dword ptr [esp] ;[esp] = n-2
        call    f               ;eax = f(n-2)
        add     eax,eax         ;eax = 2*f(n-2)
        add     ebx,eax         ;ebx = f(n-1) + 2*f(n-2)
        dec     dword ptr [esp] ;[esp] = n-3
        call    f               ;eax = f(n-3)
        add     esp,4           ;restore esp
        sub     ebx,eax         ;ebx = f(n-1) + 2*f(n-2) - f(n-3)
        mov     eax,ebx         ;eax = f(n-1) + 2*f(n-2) - f(n-3)
        pop     ebx             ;restore ebx
        ret
f       endp

main    proc    near
        push    dword ptr 0     ;[esp] = n
main0:  call    f
        push    eax
        push    offset fmt
        call    printf
        add     esp,8
        inc     dword ptr [esp]
        cmp     dword ptr [esp],20
        jl      main0
        add     esp,4
        xor     eax,eax
        ret
main    endp

Answer 2

我不明白你对 EBX 和堆栈上的第二个参数的操作。

让我们从头开始。递归函数也是一个函数。当你调用它时，你必须保留可以被函数改变的寄存器，并且你需要在函数 return 之后保持不变。该函数以不同的 n 调用自身三次，并以不同的结果运行。当您在堆栈上获得 n 以进行任意恢复时，您必须保留结果。当你将 return (funkcja(n-1)+(2*funkcja(n-2))-funkcja(n-3)); 拆分为

时，它会变得更加清晰

int result = 0;
result += funkcja(n-1);
result += ( 2 * funkcja(n-2) );
result -= funkcja(n-3);
return result;

result 是所谓的局部变量。仅此运行函数需要它，并且会随函数 return 一起丢失。局部变量通常存储在堆栈中。您不需要使用 prolog 和 epilog 构建堆栈框架，一个简单的 push/pop 组合也可以做到。

# f(n) = f(n-1) + (2*f(n-2)) - f(n-3)
# 0 1
# 1 0
# 2 1
# 3 0   1 + 0 - 1
# 4 2   0 + 2 - 0
# 5 1   2 + 0 - 1
# 6 5   1 + 4 - 0
# 7 5   5 + 2 - 2
# 8 14  5 + 10 - 1
# 9 19  14 + 10 - 5

.intel_syntax noprefix
.text
.globl main

main:

    mov eax, 9
    push eax
    call funkcja
    add esp, 4

    push eax
    mov eax, offset message
    push eax
    call printf

    add esp,8
    mov eax,0
    ret

funkcja:
    mov eax, [esp+4]
    cmp eax,3
    jge 3f

    2:
    cmp eax,2
    jne 0f
    mov eax, 1
    ret

    0:
    cmp eax,0
    jne 1f
    mov eax, 1
    ret

    1:
    xor eax, eax
    ret

    3:
    push 0                      # Result = 0

    # 1. Call
    mov eax, [esp+8]            # +8: retrieve n behind push and return address
    sub eax, 1
    push eax
    call funkcja
    add esp, 4
    add [esp], eax              # Result += EAX

    # 2. Call
    mov eax, [esp+8]            # +8: retrieve n behind push and return address
    sub eax, 2
    push eax
    call funkcja
    add esp, 4
    add eax, eax
    add [esp], eax              # Result += EAX

    # 3. Call
    mov eax, [esp+8]            # +8: retrieve n behind push and return address
    sub eax, 3
    push eax
    call funkcja
    add esp, 4
    sub [esp], eax              # Result -= EAX

    pop eax                     # Return EAX = Result
    ret

.data;
    message: .asciz "Result=%i\n"

.att_syntax prefix

汇编中的递归

Recursion in Assembly

gcc

assembly

32-bit

gnu-assembler