没有 return 语句的 gcc 中的尾递归

Question

显然以下代码在 GCC 中有效。我在 onlinegdb.

中尝试了该代码

# include <stdio.h>

int calc_gcd (int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
        calc_gcd (b, r);
    }
}

int main() {
    int a, b, gcd, dividend, divisor;
    printf ("Enter two numbers: ");
    scanf ("%d%d", &a, &b);
    dividend = (a > b) ? a : b;
    divisor = (a < b) ? a : b;
    gcd = calc_gcd (dividend, divisor);
    printf ("GCD = %d\n", gcd);
    return 0;
}

但它在 clang 13 中失败，结果如下

tail_recursion_gcd.c:15:1: warning: non-void function does not return a value in all control paths [-Wreturn-type]
}
^
1 warning generated.
Enter two numbers: 15 10
GCD = 127       // garbage

我不明白。显然 GCC 允许的并不直观，您必须从函数中 return。

我尝试了以下方法，但在 gcc 中不起作用

# include <stdio.h>

int useless_func()
{
    3050;
}
int main() {
    printf("result = %d", useless_func());
    return 0;
}

输出为result = 0

Answer 1

您的代码有问题。允许从 int 函数 return 不 returning 一个值，只有当该值永远不会被消耗时。这是 K&R C 的遗留物，不应再使用。

int calc_gcd (int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
        calc_gcd (b, r);
    }
}

显然不正确。你要。

int calc_gcd (int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
        return calc_gcd (b, r);
    }
}

事实上，这个特定的代码倾向于在 -O0 上工作，因为 return 值被遗留在寄存器中，剩下的就是你想要的 return 值。

Answer 2

TL;DR: 你老师给你的GCD函数是不可移植的。

你想要的如下：

int calc_gcd (int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
      return calc_gcd (b, r);
    }
}

您使用的是什么版本的 GCC，在什么操作系统上？

GCC 比 Clang 宽松得多。看起来 GCC 决定函数 calc_gcd 不应该失败并且应该 return calc_gcd(b, r).

的结果

当您使用 Clang 编译时，我很惊讶它没有 return 1。当我在 M1 MacBook Pro 上编译时它做到了。

来自 here:

Flowing off the end of a function is equivalent to a return with no value; this results in undefined behavior in a value-returning function.

在 x86_64 Linux 上，当调用 return 具有 non-void 值的函数时，space 被分配到 return 值。因此，没有明确的 return 声明，一些值仍然是 returned.

注意：在x86_64上，return值存储在RAX中（EAX是低位）。

我在 x86_64 Ubuntu 服务器 18.04 上使用 GCC 7.5.0 编译。我使用的命令是gcc -o gcd gcd.c -no-pie -g。这是 calc_gcd:

的程序集转储

   0x00000000004005c7 <+0>:     push   rbp
   0x00000000004005c8 <+1>:     mov    rbp,rsp
   0x00000000004005cb <+4>:     sub    rsp,0x20
   0x00000000004005cf <+8>:     mov    DWORD PTR [rbp-0x14],edi
   0x00000000004005d2 <+11>:    mov    DWORD PTR [rbp-0x18],esi
   0x00000000004005d5 <+14>:    mov    eax,DWORD PTR [rbp-0x14]
   0x00000000004005d8 <+17>:    cdq
   0x00000000004005d9 <+18>:    idiv   DWORD PTR [rbp-0x18]
   0x00000000004005dc <+21>:    mov    DWORD PTR [rbp-0x4],edx
   0x00000000004005df <+24>:    cmp    DWORD PTR [rbp-0x4],0x0
   0x00000000004005e3 <+28>:    jne    0x4005ea <calc_gcd+35>
   0x00000000004005e5 <+30>:    mov    eax,DWORD PTR [rbp-0x18]
   0x00000000004005e8 <+33>:    jmp    0x4005f9 <calc_gcd+50>
   0x00000000004005ea <+35>:    mov    edx,DWORD PTR [rbp-0x4]
   0x00000000004005ed <+38>:    mov    eax,DWORD PTR [rbp-0x18]
   0x00000000004005f0 <+41>:    mov    esi,edx
   0x00000000004005f2 <+43>:    mov    edi,eax
   0x00000000004005f4 <+45>:    call   0x4005c7 <calc_gcd>
   0x00000000004005f9 <+50>:    leave
   0x00000000004005fa <+51>:    ret

使用 Clang 6.0.0 时：

   0x0000000000400540 <+0>:     push   rbp
   0x0000000000400541 <+1>:     mov    rbp,rsp
   0x0000000000400544 <+4>:     sub    rsp,0x20
   0x0000000000400548 <+8>:     mov    DWORD PTR [rbp-0x8],edi
   0x000000000040054b <+11>:    mov    DWORD PTR [rbp-0xc],esi
   0x000000000040054e <+14>:    mov    eax,DWORD PTR [rbp-0x8]
   0x0000000000400551 <+17>:    cdq
   0x0000000000400552 <+18>:    idiv   DWORD PTR [rbp-0xc]
   0x0000000000400555 <+21>:    mov    DWORD PTR [rbp-0x10],edx
   0x0000000000400558 <+24>:    cmp    DWORD PTR [rbp-0x10],0x0
   0x000000000040055c <+28>:    jne    0x40056d <calc_gcd+45>
   0x0000000000400562 <+34>:    mov    eax,DWORD PTR [rbp-0xc]
   0x0000000000400565 <+37>:    mov    DWORD PTR [rbp-0x4],eax
   0x0000000000400568 <+40>:    jmp    0x40057b <calc_gcd+59>
   0x000000000040056d <+45>:    mov    edi,DWORD PTR [rbp-0xc]
   0x0000000000400570 <+48>:    mov    esi,DWORD PTR [rbp-0x10]
   0x0000000000400573 <+51>:    call   0x400540 <calc_gcd>
   0x0000000000400578 <+56>:    mov    DWORD PTR [rbp-0x14],eax
   0x000000000040057b <+59>:    mov    eax,DWORD PTR [rbp-0x4]
   0x000000000040057e <+62>:    add    rsp,0x20
   0x0000000000400582 <+66>:    pop    rbp
   0x0000000000400583 <+67>:    ret

你可以看到编译器在优化方面做出了不同的选择。

事实上，对于 GCC，rbp-0x18 等于 0x00000005 +38。对于 Clang，rbp-0x4 等于完全不同的东西。在我的机器上，在 pwndbg 中，它是 0x00007fff.

没有 return 语句的 gcc 中的尾递归

tail recursion in gcc without return statement

c

recursion

gcc

function

clang