Question

所谓 尾调用 （tail call）就是执行流的最后一个行为是函数调用。

void test ()
{
    char *s = "hello";
    puts(s);            // 尾调用。
}

int test ()
{
    int x = 100;
    int y = 200;
    return add(x, y) + 1;  // 不是尾调用。
}

int test ()
{
    int x = 100;
    int y = 200;
    return add(x, y);     // 尾调用。
}

int test ()
{
    int x = 100;
    int y = 200;
    int z = add(x, y);    // 尾调用。
    return z;
}

看看编译器针对尾调用会做什么？

#include <stdio.h>
#include <stdlib.h>

__attribute__(( noinline )) void test ()
{
    char *s = "hello";
    puts(s);
}

int main (void) 
{
    test();    
    return 0;
}

$ gcc -O2 -o test main.c
$ objdump -d -M intel ./test | grep -A10 "<test>:"
    
0000000000001170 <test>:
    1170:	f3 0f 1e fa          	endbr64 
    1174:	48 8d 3d 89 0e 00 00 	lea    rdi,[rip+0xe89]
    117b:	e9 d0 fe ff ff       	jmp    1050 <puts@plt>

函数 test 最后一个 puts 语句是尾调用，优化模式编译后使用 jmp 代替 call 指令。

__attribute__(( noinline )) int add (int x, int y)
{
    return x + y;
}

__attribute__(( noinline )) int test ()
{
    int x = 100;
    int y = 200;
    return add(x, y);       // 尾调用。
}

$ gcc -O2 -o test main.c
$ objdump -d -M intel ./test | grep -A10 "<test>:"

0000000000001150 <test>:
    1150:	f3 0f 1e fa          	endbr64 
    1154:	be c8 00 00 00       	mov    esi,0xc8
    1159:	bf 64 00 00 00       	mov    edi,0x64
    115e:	eb e0                	jmp    1140 <add>

如果不是尾调用，则继续使用 call 指令。

__attribute__(( noinline )) int test ()
{
    int x = 100;
    int y = 200;
    return add(x, y) + 1;   // 不是尾调用。
}

$ gcc -O2 -o test main.c
$ objdump -d -M intel ./test | grep -A10 "<test>:"

0000000000001150 <test>:
    1150:	f3 0f 1e fa          	endbr64 
    1154:	be c8 00 00 00       	mov    esi,0xc8
    1159:	bf 64 00 00 00       	mov    edi,0x64
    115e:	e8 dd ff ff ff       	call   1140 <add>
    1163:	83 c0 01             	add    eax,0x1
    1166:	c3                   	ret  

最后语句是函数调用，就连返回值都由被调用函数提供。那么当前栈帧状态就 “无需保留”，内存可被后续函数复用。这显然对 递归调用 （recursion）非常有利，可避免过多栈帧导致导致 堆栈溢出 （stack overflow)。当然，前提是这个递归函数是尾调用实现。

#include <stdio.h>
#include <stdlib.h>

__attribute__((noinline)) long long fact_aux (int n, long long result) 
{
    if (n < 2) return result;
    return fact_aux(n - 1, result * n);
}

int main (void) 
{
    printf("%lld\n", fact_aux(3, 1));
    return 0;
}