Examples of successful tail call optimization in C

O1.s

	.file	"tco.c"
	.text
	.globl	fib_tailrec_
	.type	fib_tailrec_, @function
fib_tailrec_:
.LFB21:
	.cfi_startproc
	movl	%edi, %eax
	testl	%edi, %edi
	je	.L7
	movl	%edx, %ecx
	movl	%edx, %eax
	cmpl	$1, %edi
	je	.L7
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	leal	(%rsi,%rdx), %edx
	subl	$1, %edi
	movl	%ecx, %esi
	call	fib_tailrec_
	addq	$8, %rsp
	.cfi_def_cfa_offset 8
.L7:
	rep ret
	.cfi_endproc
.LFE21:
	.size	fib_tailrec_, .-fib_tailrec_
	.globl	b
	.type	b, @function
b:
.LFB22:
	.cfi_startproc
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	movl	$1, %edx
	movl	$0, %esi
	movl	$20, %edi
	call	fib_tailrec_
	addq	$8, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE22:
	.size	b, .-b
	.globl	a
	.type	a, @function
a:
.LFB23:
	.cfi_startproc
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	call	b
	addq	$8, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE23:
	.size	a, .-a
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB24:
	.cfi_startproc
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	call	a
	movl	%eax, %esi
	movl	$.LC0, %edi
	movl	$0, %eax
	call	printf
	movl	$0, %eax
	addq	$8, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE24:
	.size	main, .-main
	.ident	"GCC: (SUSE Linux) 4.8.1 20130909 [gcc-4_8-branch revision 202388]"
	.section	.note.GNU-stack,"",@progbits

O2.s

	.file	"tco.c"
	.text
	.p2align 4,,15
	.globl	fib_tailrec_
	.type	fib_tailrec_, @function
fib_tailrec_:
.LFB21:
	.cfi_startproc
	testl	%edi, %edi
	je	.L5
	cmpl	$1, %edi
	jne	.L3
	jmp	.L10
	.p2align 4,,10
	.p2align 3
.L4:
	cmpl	$1, %edi
	je	.L2
	movl	%edx, %esi
	movl	%eax, %edx
.L3:
	subl	$1, %edi
	leal	(%rsi,%rdx), %eax
	jne	.L4
.L5:
	xorl	%eax, %eax
	ret
.L10:
	movl	%edx, %eax
	.p2align 4,,10
	.p2align 3
.L2:
	rep ret
	.cfi_endproc
.LFE21:
	.size	fib_tailrec_, .-fib_tailrec_
	.p2align 4,,15
	.globl	b
	.type	b, @function
b:
.LFB22:
	.cfi_startproc
	movl	$1, %edx
	xorl	%esi, %esi
	movl	$20, %edi
	jmp	fib_tailrec_
	.cfi_endproc
.LFE22:
	.size	b, .-b
	.p2align 4,,15
	.globl	a
	.type	a, @function
a:
.LFB23:
	.cfi_startproc
	jmp	b
	.cfi_endproc
.LFE23:
	.size	a, .-a
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4,,15
	.globl	main
	.type	main, @function
main:
.LFB24:
	.cfi_startproc
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	call	a
	movl	$.LC0, %edi
	movl	%eax, %esi
	xorl	%eax, %eax
	call	printf
	xorl	%eax, %eax
	addq	$8, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE24:
	.size	main, .-main
	.ident	"GCC: (SUSE Linux) 4.8.1 20130909 [gcc-4_8-branch revision 202388]"
	.section	.note.GNU-stack,"",@progbits

tco.c

#include <stdio.h>

// Tail-recursive Fibonacci using two accumulators
#define fib_tailrec(n) fib_tailrec_(n, 0, 1)

int __attribute__((noinline)) fib_tailrec_(int n, int a, int b)
{
	if (n == 0)
		return n;
	if (n == 1)
		return b;
	else
		return fib_tailrec_(n-1, b, a+b);
}

int __attribute__((noinline)) b(void)
{
	return fib_tailrec(20);
}

int __attribute__((noinline)) a(void)
{
	return b();
}

int main(void)
{
	printf("%d\n", a());

	return 0;
}

http://david.wragg.org/blog/2014/02/c-tail-calls-1.html shows some code that can prevent optimization of tail calls.