Recursion in Assembly

Question

I need help with Assembly code which I just started learning.

.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; 

In main function 'eax' register is used as a 'n' parameter for function that:

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);

So for n=3 function returns 0, n=4 returns 2, n=5 returns 1, n=6 returns 5 e.t.c.

The recursion is pretty problematic, for values < 5 fuction works fine, but for 6, 7 e.t.c. function returns tremendously high or low (negative) values. I've been working on it for +10 hours, and I can't manage to make it work property. What am I doing wrong?

It is required to use "PUSH" and "[esp+4]", "add esp,4;" and other simple instructions that are already in the code. Program is compiled under -m32 command parameter(gcc -Wall funcas.s -m32 -o test).

I wrote down the same code in C to show what i'm trying to achieve

#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

The problem is that the code keeps accumulating all of the results. Change f to only use one parameter. Example Microsoft type assembler code. In both f() and main(), n is stored on the stack.

        .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

I don't understand your action with EBX and the second argument on the stack.

Let's start from scratch. A recursive function is a function as well. When you call it you have to preserve registers which can be altered by the function and you need unaltered after the function return. The function calls itself three times with different n and operates with the different results. While you've got n on the stack for arbitrary recovery, you have to preserve the results. It becomes more clear when you split return (funkcja(n-1)+(2*funkcja(n-2))-funkcja(n-3)); into

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

result is a so called local variable. It's only needed for this run of the function and will lost with the function return. A local variable is usually stored on the stack. You don't need to build a stackframe with prolog and epilog, a simple push/pop combination will do it as well.

# 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