Alex Rivera | Logout

Optimizations by compiler in a recursive program

Asked 2012-03-22T14:37:39.953
8

I got motivated from tail call optimization question What Is Tail Call Optimization?

So, I decided to see how can I do it in plain C.

So, I wrote the 2 factorial programs, 1st where tail call optimization can be applied. I call this fact function as fact(n, 1).

unsigned long long int fact(int n, int cont)
{
      if(n == 0)
            return cont;

      else return fact(n-1, n * cont);
}

2nd is the normal recursion where multiple stack frames are required.

unsigned long long int fact(int n)
{
    if(n == 0)
        return 1;

    else return n * fact(n-1);
}

This is the assembly generated by a 32 bit compiler for the former with -O2

0x8048470 <fact>:   push   %ebp
0x8048471 <fact+1>: mov    %esp,%ebp
0x8048473 <fact+3>: mov    0x8(%ebp),%edx
0x8048476 <fact+6>: mov    0xc(%ebp),%eax
0x8048479 <fact+9>: test   %edx,%edx
0x804847b <fact+11>:    je     0x8048488 <fact+24>
0x804847d <fact+13>:    lea    0x0(%esi),%esi
0x8048480 <fact+16>:    imul   %edx,%eax
0x8048483 <fact+19>:    sub    $0x1,%edx
0x8048486 <fact+22>:    jne    0x8048480 <fact+16>
0x8048488 <fact+24>:    mov    %eax,%edx
0x804848a <fact+26>:    sar    $0x1f,%edx
0x804848d <fact+29>:    pop    %ebp
0x804848e <fact+30>:    ret    

This is the assembly generated by a 32 bit compiler for latter with -O2.

0x8048470 <fact>:   push   %ebp
0x8048471 <fact+1>: mov    %esp,%ebp
0x8048473 <fact+3>: push   %edi
0x8048474 <fact+4>: push   %esi
0x8048475 <fact+5>: push   %ebx
0x8048476 <fact+6>: sub    $0x14,%esp
0x8048479 <fact+9>: mov    0x8(%ebp),%eax
0x804847c <fact+12>:    movl   $0x1,-0x18(%ebp)
0x8048483 <fact+19>:    movl   $0x0,-0x14(%e
Edit
Report

1 Answer

4

The difference is that the first version uses an int variable for the calculation, which is then extended to unsigned long long at the end, while the latter uses an unsigned long long all the way.

answered 2012-03-22T18:10:45.623

Your Answer