昨天有位小大一來問問題，他寫的code在local可以跑，但是上傳到Judgegirl都是wrong answer。
我看了一下題目，是要用遞迴計算 \(1^2 + 2^2 + \ldots + n^2\) 。他的code大概長這樣：
#include <stdio.h>
int squares(int n)
{
int t = 0;
if (n == 1)
{
t += 1;
return t;
}
else
{
t += n * n + squares (n - 1);
return;
}
}
int main()
{
printf("%d\n", squares (5));
return 0;
}
用gcc編譯：gcc squares.c
執行結果：
$ ./a.out
55
看起來是對的，\(1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55\)，為何judge不過？
其實滿明顯的，第二個return應該是return t才對。
問題來了，為何結果是對的？
這得從x86 calling convention開始講起（維基百科）。一般的x86程式中，函數執行到return時是把return value放進eax暫存器中，然後jump回去。看看這兩個函數的assembly即可見真章：
$ gdb ./a.out
Reading symbols from ./a.out...(no debugging symbols found)...done.
(gdb) disassemble squares
Dump of assembler code for function squares:
0x0000000000400506 <+0>: push rbp
0x0000000000400507 <+1>: mov rbp,rsp
0x000000000040050a <+4>: push rbx
0x000000000040050b <+5>: sub rsp,0x28
0x000000000040050f <+9>: mov DWORD PTR [rbp-0x24],edi
0x0000000000400512 <+12>: mov DWORD PTR [rbp-0x14],0x0
0x0000000000400519 <+19>: cmp DWORD PTR [rbp-0x24],0x1
0x000000000040051d <+23>: jne 0x400528 <squares+34>
0x000000000040051f <+25>: add DWORD PTR [rbp-0x14],0x1
0x0000000000400523 <+29>: mov eax,DWORD PTR [rbp-0x14]
0x0000000000400526 <+32>: jmp 0x400543 <squares+61>
0x0000000000400528 <+34>: mov eax,DWORD PTR [rbp-0x24]
0x000000000040052b <+37>: imul eax,DWORD PTR [rbp-0x24]
0x000000000040052f <+41>: mov ebx,eax
0x0000000000400531 <+43>: mov eax,DWORD PTR [rbp-0x24]
0x0000000000400534 <+46>: sub eax,0x1
0x0000000000400537 <+49>: mov edi,eax
0x0000000000400539 <+51>: call 0x400506 <squares>
0x000000000040053e <+56>: add eax,ebx
0x0000000000400540 <+58>: add DWORD PTR [rbp-0x14],eax
0x0000000000400543 <+61>: add rsp,0x28
0x0000000000400547 <+65>: pop rbx
0x0000000000400548 <+66>: pop rbp
0x0000000000400549 <+67>: ret
End of assembler dump.
(gdb) disassemble main
Dump of assembler code for function main:
0x000000000040054a <+0>: push rbp
0x000000000040054b <+1>: mov rbp,rsp
0x000000000040054e <+4>: mov edi,0x5
0x0000000000400553 <+9>: call 0x400506 <squares>
0x0000000000400558 <+14>: mov esi,eax
0x000000000040055a <+16>: mov edi,0x4005f4
0x000000000040055f <+21>: mov eax,0x0
0x0000000000400564 <+26>: call 0x4003e0 <printf@plt>
0x0000000000400569 <+31>: mov eax,0x0
0x000000000040056e <+36>: pop rbp
0x000000000040056f <+37>: ret
End of assembler dump.
DWORD PTR [rbp-0x24]是edi，也就是第一個function argument rdi的lower bits，換句話說就是n。squares+34把n的值放到eax，squares+41之後ebx的值是n * n。squares+43～squares+51把squares(n - 1)的值算出來放到eax，squares+56之後eax的值就是n * n + squares(n - 1)。這時候直接return答案剛好會是對的。
就這樣，一連串的剛剛好，最後出來剛好結果是對的。然而judge上的compiler跟我們自己的compiler不一定一樣，這種undefined behavior，結果就很難說了。
這樣的解釋，學弟好像聽不太懂，不過沒關係，岱神聽懂就好了^__^