C code understandings conversion to assembly (MIPS)

Hi ,
I totally understand the recursion in C programming and now trying more further to understand what is going behind the scenes , so trying please to have the conversion on assembly language for this chunk of code ( just for more understandings not more ) .

C code is :

Code:

---

int divide(int a)
{
  if ( a > 1 )
  {
    return divide(a/2);
    }
  return a;
}

---

Could anyone please help me for conversion this code to assembly language?
like normally Im not programming on assembly language and learnt it long long time ago but trying to understand only
the recursion part how it's done on assembly behind.


thanks much

Simple:

Code:

---

$ gcc -S divide.c

// divide.s

        .file  "divide.c"
        .text
        .globl  divide
        .type  divide, @function
divide:
.LFB0:
        .cfi_startproc
        pushq  %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $16, %rsp
        movl    %edi, -4(%rbp)
        cmpl    $1, -4(%rbp)
        jle    .L2
        movl    -4(%rbp), %eax
        movl    %eax, %edx
        shrl    $31, %edx
        addl    %edx, %eax
        sarl    %eax
        movl    %eax, %edi
        call    divide
        jmp    .L3
.L2:
        movl    -4(%rbp), %eax
.L3:
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size  divide, .-divide
        .ident  "GCC: (Debian 13.2.0-10) 13.2.0"
        .section        .note.GNU-stack,"",@progbits

---

Quote:

---

Originally Posted by rstanley

Simple:

---

Not MIPS...

Quote:

---

Originally Posted by flp1969

Not MIPS...

---

MIPS cross compile with gcc.

I don't use MIPS.

Try Compiler Explorer -- Matt Godbolt's "Compiler Explorer" website. You can select a MIPS compiler, and choose which one you like best, then generate assembly from whatever C code you post up.

> the recursion part how it's done on assembly behind.
Exactly the same way one function would call another.

Nothing changes except for the name of the called function.

For recursive functions, you end up with 3 cases - depending on the function and how smart the compiler is.
1. A recursive call
2. Tail call elimination, the call becomes a jump back to the start - Tail call - Wikipedia
3. Complete elimination of any looping at all.

For example, your divide reduces to this at -O2

Code:

---

divide(int):
        test    edi, edi
        mov    eax, 1
        cmovle  eax, edi
        ret

---

No recursion, no loops, just the trivial answer.

In other words, the compiler you used (GCC?) is smart enough to optimize the recursive code to the equivalent to this code:

Code:

---

int divide(int a)
{
    if (a > 1) {
        return 1;
    }
    return a;
}

---

Quote:

---

Originally Posted by christop

In other words, the compiler you used (GCC?) is smart enough to optimize the recursive code to the equivalent to this code:

Code:

---

int divide(int a)
{
    if (a > 1) {
        return 1;
    }
    return a;
}

---

---

why if (a>1) then you return 1? my original function is return divide(a/2) ;

Quote:

---

Originally Posted by Salem

> the recursion part how it's done on assembly behind.
Exactly the same way one function would call another.

Nothing changes except for the name of the called function.

For recursive functions, you end up with 3 cases - depending on the function and how smart the compiler is.
1. A recursive call
2. Tail call elimination, the call becomes a jump back to the start - Tail call - Wikipedia
3. Complete elimination of any looping at all.

For example, your divide reduces to this at -O2

Code:

---

divide(int):
        test    edi, edi
        mov    eax, 1
        cmovle  eax, edi
        ret

---

No recursion, no loops, just the trivial answer.

---

I understand , thanks.



like what Im trying to understand why we need to avoid generally recursion .. any reason aside to stackover flow case?? there is also another reason which is related to "functions calling overheads" but I didnt get it to be honest if someone can help please ..

assume I have two following equivalent solutions :

Code:

---

intdivide(inta){
    if (a > 1) {
        return 1;
    }
    return a;
}


---

second solution equivalent for first recursion solution is " for loop solution " :

Code:

---

---

Code:

---

int divide(int a)
{
for ( ; a > 1 ; a/=2);
return a;
}


---

why for loop solution is more efficient to use than recursion solutions? what the are the reasons for choosing for loop solution upon recursive? ..

additional quivery , is the number of iterations of for loop itself is same as the number of functions calling on recursive solution? if yes/no then why ?

There's no reason to avoid it per se, it just comes with a few health warnings - like the aforementioned stack overflow potential.

Anything you can do with recursion, you can do with a for loop (and a queue data structure if you do need to store intermediate state between iterations).

> why for loop solution is more efficient to use than recursion solutions?
There's no function call overhead.

> what the are the reasons for choosing for loop solution upon recursive? ..
There's no function call overhead, and no chance of blowing the stack.
You can write strlen() as a recursive function. You'd be dumb to try it on a real long string though.

> additional quivery , is the number of iterations of for loop itself is same as the number of functions calling on recursive solution? if yes/no then why ?
Should be the same, unless you've done something wrong.

Quote:

---

Originally Posted by Salem

There's no reason to avoid it per se, it just comes with a few health warnings - like the aforementioned stack overflow potential.

Anything you can do with recursion, you can do with a for loop (and a queue data structure if you do need to store intermediate state between iterations).

> why for loop solution is more efficient to use than recursion solutions?
There's no function call overhead.

> what the are the reasons for choosing for loop solution upon recursive? ..
There's no function call overhead, and no chance of blowing the stack.
You can write strlen() as a recursive function. You'd be dumb to try it on a real long string though.

> additional quivery , is the number of iterations of for loop itself is same as the number of functions calling on recursive solution? if yes/no then why ?
Should be the same, unless you've done something wrong.

---

thanks much , some inline comments as you see below.

> There's no function call overhead.
when you say function overhead what do you mean exactly could you elaborate please meaning of function overheads and how that impact stack / time complexity? why for loop doesnt have function overheads?

>Should be the same, unless you've done something wrong.
why number of calling functions on recursive shall be same as number of iterations? ... maybe if you can give please calculation how did you validate about that would be much worthy ..

Write recursive and non-recursive versions of some functions and count for yourself.

You want to understand - write some code!

Quote:

---

Originally Posted by Salem

Write recursive and non-recursive versions of some functions and count for yourself.

You want to understand - write some code!

---

I understand but I already wrote the code for loop solution and recursive solution above , so then what next step shall I do for proving what you're suggesting that recursive call counts same as for loop iterations counts?
you know we are talking about "n" number so cant count .. it might be that n very huge number yeah ..it's integer ..

Show us what you have so far.

Quote:

---

Originally Posted by Salem

Show us what you have so far.

---

first recursive solution

Code:

---

int divide(int a)
{
    if (a > 1) {
          return divide (a/2);
                  }
    return a;
}

---

second equivalent solution by for loop approach :

Code:

---

int divide(int a)
{
    for( ; a > 1 ; a /=2 );
    return a;
}

---

both solutions are equivalent and this what I reached so far.