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