# Recursive 版本的二進位加法

Recursive Function 問題
大家早安，我在用遞迴實作二進位加法 的時候，
如果我把最後一行的 return 拿掉，並用 gdb 觀察，
發現程式的行為並不會改變，那這個 return 是否有必要加呢？
還是我對 recursive 有什麼誤解？
以下是我的程式碼：
謝謝。
[討論串](https://www.facebook.com/groups/system.software2020/permalink/437196997214505/?__cft__[0]=AZV_gRiCpD80VqBhCy9izPoXBK5LuPYzZhSA0DRcIMLjZMrBvJS1xahlx21l_7lj-zWSQYrvphahzMJa25L_1TyqL1RnMY0wWb_TVc5K7um7G9SlzeD9-1FxIRZ9kkhMV9NsfCt_ow4pcMnz5ggBkVXBo6J_v8TNaU18sEaVX84S7VTtg547KeUBAIgL6JAFJ-s&__tn__=%2CO%2CP-R)
## 完整程式碼

#include <stdio.h>
#include <stdlib.h>
int adder(int a, int b)
{
    int sum = a ^ b;
    int carry = a & b;
    if (carry == 0)
        return sum;
    adder(sum, carry << 1);
}

int main(int argc, char **argv)
{
    if (argc != 3) {
        printf("Usage: ./adder a b\n");
        return -1;
    }
    int a=atoi(argv[1]);
    int b=atoi(argv[2]);
    int result = adder(a, b);
    printf("%d + %d = %d", a, b, result);
}

## 測試方法
使用 gdb 並設置 break point 在 adder 這個 function, 與第十行，也就是 adder這個 function 結束的地方。
測試參數: `a = 3, b = 2`

### 情況一: line 9 沒有加上 return

int adder(int a, int b)
{
    int sum = a ^ b;
    int carry = a & b;
    if (carry == 0)
        return sum;
    adder(sum, carry << 1);
}

(gdb) b adder
Breakpoint 1 at 0x6d8: file adder.c, line 5.
(gdb) b 10
Breakpoint 2 at 0x707: file adder.c, line 10.
(gdb) r 3 2
Starting program: /home/ubuntu/sandbox/adder/adder 3 2

Breakpoint 1, adder (a=3, b=2) at adder.c:5
5	    int sum = a ^ b;
(gdb) n
6	    int carry = a & b;
(gdb) n
7	    if (carry == 0)
(gdb) n
9	    adder(sum, carry << 1);
(gdb) n

Breakpoint 1, adder (a=1, b=4) at adder.c:5
5	    int sum = a ^ b;
(gdb) n
6	    int carry = a & b;
(gdb) n
7	    if (carry == 0)
(gdb) n
8	        return sum;
(gdb) n

Breakpoint 2, adder (a=1, b=4) at adder.c:10
10	}
(gdb) n

Breakpoint 2, adder (a=3, b=2) at adder.c:10
10	}
(gdb) n
main (argc=3, argv=0x7fffffffe4c8) at adder.c:21
21	    printf("%d + %d = %d", a, b, result);
(gdb) n
22	}
(gdb) n
__libc_start_main (main=0x555555554709 <main>, argc=3, argv=0x7fffffffe4c8, init=<optimized out>, fini=<optimized out>,
    rtld_fini=<optimized out>, stack_end=0x7fffffffe4b8) at ../csu/libc-start.c:344
344	../csu/libc-start.c: No such file or directory.
(gdb) n
3 + 2 = 5[Inferior 1 (process 31573) exited normally]

### 情況二: line 9 加上 return

--- a/adder/adder.c
+++ b/adder/adder.c
@@ -6,7 +6,7 @@ int adder(int a, int b)
     int carry = a & b;
     if (carry == 0)
         return sum;
-    adder(sum, carry << 1);
+    return adder(sum, carry << 1);
 }

(gdb) b 10
Breakpoint 1 at 0x707: file adder.c, line 10.
(gdb) b adder
Breakpoint 2 at 0x6d8: file adder.c, line 5.
(gdb) r 3 2
Starting program: /home/ubuntu/sandbox/adder/adder 3 2

Breakpoint 2, adder (a=3, b=2) at adder.c:5
5	    int sum = a ^ b;
(gdb) n
6	    int carry = a & b;
(gdb) n
7	    if (carry == 0)
(gdb) n
9	    return adder(sum, carry << 1);
(gdb) n

Breakpoint 2, adder (a=1, b=4) at adder.c:5
5	    int sum = a ^ b;
(gdb) n
6	    int carry = a & b;
(gdb) n
7	    if (carry == 0)
(gdb) n
8	        return sum;
(gdb) n

Breakpoint 1, adder (a=1, b=4) at adder.c:10
10	}
(gdb) n

Breakpoint 1, adder (a=3, b=2) at adder.c:10
10	}
(gdb) n
n
main (argc=3, argv=0x7fffffffe4c8) at adder.c:21
21	    printf("%d + %d = %d", a, b, result);
(gdb) n
22	}
(gdb) n
__libc_start_main (main=0x555555554709 <main>, argc=3, argv=0x7fffffffe4c8, init=<optimized out>, fini=<optimized out>,
    rtld_fini=<optimized out>, stack_end=0x7fffffffe4b8) at ../csu/libc-start.c:344
344	../csu/libc-start.c: No such file or directory.
(gdb) n
3 + 2 = 5[Inferior 1 (process 31628) exited normally]

## 討論區節錄
>注意編譯器的警告訊息: "warning: control may reach end of non-void function [-Wreturn-type]" 在移去 return 關鍵字的狀況下，產生出來的機械碼就取決於編譯器內部實作，而非 C 語言規範
>:notes: Jserv老師
補上資料
[x86-64 clang 10.0.0](https://godbolt.org/z/5vxKPz) (移除 return 關鍵字)

<source>:10:1: warning: non-void function does not return a value in all control paths [-Wreturn-type]

}

^

1 warning generated.

>x86 的 return 值會放在 eax，如果沒有 return，對 caller 而言會把 eax 中的數值視為 return 值
>[name=翁愷邑]
>因為x86的calling convention會把return value用eax來存。那如果沒有在callee結尾加return，其實gcc compiler還是會把調整stack跳回caller做好，所以這時候caller拿到的return value就是eax，然後剛好你在返回caller的時候，eax都沒動到
>[name=陳廣翰]
>補充一下 http://c0x.coding-guidelines.com/6.9.1.html 1844行有說此行為是ub
>[name=Yeting Kuo]
>
>使用 gcc 10.2 可以看到兩者一樣, 但換成
使用 clang 10.0 就變成剛好就差一個 mov eax 所以才會出錯
>[比較 x86-64 clang 10.0.0 編出的 assembly: 有 return v.s. 沒有 return](https://godbolt.org/z/veW156)
>[name=翁愷邑]
## TODO: 了解函式呼叫的 assembly code
[你所不知道的 C 語言：函式呼叫篇](/@sysprog/c-function?type=view)