(Homework) Translating a C recursive function to assembly (AT&T syntax)

Question

Here is my C Code:

void combinationComputer(int* temp, int* arr, int* data, int start, int end,
                         int index, int k, int* x, int* y, int count) {
    int i;

    if (index == k) {
        if (count > k) {
            *x = *x + k;
            *y = *y + k;
        }

        for (i = *x; i < *y; i++)
            temp[i] = data[i - *x]; // storing all combinations into temp[] as a
                                    // single chunk, one combination at a time

        return;
    }

    for (i = start; i <= end && end - i + 1 >= k - index; i++) {
        data[index] = arr[i]; // each combination is stored in data[], with each
                              // subsequent combination overwriting the previous
                              // one.
        count = count + 1;
        combinationComputer(temp, arr, data, i + 1, end, index + 1, k, x, y,
                            count); // recursive call
    }
}

What this function does is not very relevant to the question, I'm just stuck on the for loop after return. See this for loop calls the function recursively. Eventually the for loop will not hold true, and it will just exit the function by reaching the last brackets.

In C, this automatically returns control back to the parent call to combinationComputer, inside this for loop. I'm not sure how to implement this in assembly. Is there a specific name for this behavior in C? (Is it tail-call elimination)?

Basically what I am asking is what is the behavior called when you exit (by reaching the last bracket) a function called recursively and it returns to the parent call. How can this be implemented in assembly (no code please, just logic) If you need more information please ask.

A void function which reaches the ending brace performs a return, just as though you'd put return; there explicitly. It's done exactly the same as the first return;, usually with a ret instruction. Tail-call elimination is something else entirely, and it's inapplicable here because the recursive calls are not in tail position. — Iwillnotexist Idonotexist
– Iwillnotexist Idonotexist, Commented May 19, 2015 at 4:28
Ok I didn't know that. Thanks. Post it as the answer. and I'll pick it. — adrotter
– adrotter, Commented May 19, 2015 at 4:42
"Translating a C […] function to assembly" — you should use a C compiler for that. — The Paramagnetic Croissant
– The Paramagnetic Croissant, Commented May 19, 2015 at 5:46
Check your C compiler for an option that generates assembly source (usually it's -S (captial 'S')). Then you can edit that for readability and tweaking. — lurker
– lurker, Commented May 19, 2015 at 12:37

NetVipeC · Accepted Answer · 2015-05-19 21:18:19Z

First, some important instructions in assembly:

CALL: push the address of the next instruction to be executed after the call and call a function or method.
RET: pop the top element of the stacks and jump to that address.
Stack: the stack is you friend for passing variables from one recursive call to the other when register are not available.

For learn more about intel instructions look: Intel Manuals

Some sample code (of fibbonacci in asm):

  mov eax, 10     # calculating fib(10)
  call fib        # eax contain the fib to calc
  .. PRINT fib result in eax ..
  ..

proc fib:
  cmp eax, 0     # checking for final conditions 0 or 1
  jnz continue1;
  mov ebx, 1     # returning 1 for fib(0)
  ret
continue1:
  cmp eax, 1
  jnz continue2
  mov ebx, 1     # returning 0 for fib(1)
  ret
continue2:
  dec eax        # decrementing the **n** value to calc (the first
  push eax       # saving n-1
  call fib       # calc fib(n-1)
  mov edx, eax   # saving result in edx
  pop eax        # restoring n-1 in eax
  dec eax
  call fib       # calc fib(n-2)
  add edx, eax   # add to the previos fib(n-1)
  ret

You could use gcc -o [.asm output file] -S [.c to compile] and read the output to learn much more about code generation.

Collectives™ on Stack Overflow

(Homework) Translating a C recursive function to assembly (AT&T syntax)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related