C 語言遞歸二分查找缺失 return 導致錯誤返回值分析

錯誤代碼

int binary_Search(int a[], int low, int high, int key) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == key) return mid;
    if (a[mid] < key) binary_Search(a, mid+1, high, key); // 缺失 return
    if (a[mid] > key) binary_Search(a, low, mid-1, key); // 缺失 return
    // 隱式返回不確定值（通常為 0 或棧垃圾）
}

現象：`mid` 明明是 2，`result` 卻收到 1。

根本原因

遞歸調用**必須用 `return` 傳遞返回值**層層回溯。缺失 `return` 導致：

1. 深層遞歸找到目標，返回 `mid` (如 2)。
2. 上一層調用處**未接收返回值**，函數體執行完隱式返回（C99 前無返回值行為未定義，通常為 0 或棧殘留）。
3. 層層回溯最終 `main` 接收到垃圾值（如 1）。

修正代碼

int binary_Search(int a[], int low, int high, int key) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == key) return mid;
    if (a[mid] < key) return binary_Search(a, mid+1, high, key); // 加 return
    if (a[mid] > key) return binary_Search(a, low, mid-1, key); // 加 return
    return -1; // 防御性編程，理論不可達
}

編譯器警告

現代編譯器 (GCC/Clang/MSVC `-Wall` / `/W4`) 會報警：

warning: control reaches end of non-void function [-Wreturn-type]

務必開啟最高警告等級並視為錯誤 (`-Werror` / `/WX`)，編譯期直接攔截此類低級 Bug。

遞歸返回值傳遞模板

ReturnType recursive(Params) {
    if (baseCase) return baseValue;
    // 處理邏輯...
    return recursive(subParams); // 核心：return + 遞歸調用
}

總結

遞歸函數的返回值像接力棒，**每一層都必須用 `return` 向上傳遞**。缺失 `return` 是 C/C++ 遞歸編程的頭號殺手，靜態分析工具與編譯器警告是最強防線。