C 語言遞歸實現十進制轉二進制算法詳解

C 語言遞歸實現十進制轉二進制算法詳解

遞歸是解決進制轉換問題的經典方法，利用「除基取餘、逆序輸出」的數學原理，配合遞歸調用棧的後進先出特性，自然實現逆序輸出。本文詳細解析算法邏輯、代碼實現與邊界處理。

數學原理

十進制整數 N 轉二進制：

1. 反復除以 2，記錄餘數（0 或 1）
2. 商繼續除以 2，直到商為 0
3. 餘數**逆序**排列即為二進制表示

例：13 → 1101

13 / 2 = 6 ... 1
 6 / 2 = 3 ... 0
 3 / 2 = 1 ... 1
 1 / 2 = 0 ... 1
讀餘數逆序：1101

遞歸實現代碼

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

// 遞歸函數：打印 num 的二進制表示
void print_binary(int num) {
    if (num == 0) {
        return;  // 基線條件：遞歸終止
    }
    print_binary(num / 2);      // 遞歸處理高位
    printf("%d", num % 2);      // 回溯時打印低位（逆序輸出關鍵）
}

int main() {
    int num = 0;
    printf("請輸入要轉換的十進制非負整數: ");
    scanf("%d", &num);

    if (num < 0) {
        printf("暫不支持負數轉換\n");
        return 1;
    }

    printf("二進制表示: ");
    if (num == 0) {
        printf("0");  // 特殊情況：0 直接輸出
    } else {
        print_binary(num);
    }
    printf("\n");

    system("pause");  // Windows 專用，防控制台關閉
    return 0;
}

遞歸執行流程圖解（以 6 為例）

print_binary(6)
│
├─ print_binary(3)       // 6/2=3
│  │
│  ├─ print_binary(1)    // 3/2=1
│  │  │
│  │  ├─ print_binary(0) // 1/2=0 → 返回
│  │  │
│  │  └─ printf("%d", 1%2) → 輸出 '1'
│  │
│  └─ printf("%d", 3%2) → 輸出 '1'
│
└─ printf("%d", 6%2) → 輸出 '0'

最終輸出: 110 (即 6 的二進制)

關鍵點深度解析

1. 遞歸三要素

2. 為什麼打印在遞歸調用**之後**？

• 先遞歸到最深層（最高位）
• 回溯時從最高位到最低位依次打印
• 完美匹配「逆序輸出」需求，無需額外數組存儲

3. 特殊情況處理

• 輸入 0：遞歸函數直接返回無輸出，主函數需單獨處理
• 負數：本實現不支持，擴展需處理補碼或符號位
• 大數：int 範圍內安全，long long 同理

迭代版本對比

// 迭代實現：需額外數組存儲餘數再逆序輸出
void print_binary_iter(int num) {
    if (num == 0) { printf("0"); return; }
    int bits[32];  // 足夠 32 位整數
    int idx = 0;
    while (num > 0) {
        bits[idx++] = num % 2;
        num /= 2;
    }
    for (int i = idx - 1; i >= 0; i--) {
        printf("%d", bits[i]);
    }
}

優缺點對比

進階擴展：通用進制轉換

void print_base(int num, int base) {
    static const char digits[] = "0123456789ABCDEF";
    if (num == 0) return;
    print_base(num / base, base);
    putchar(digits[num % base]);
}
// 支持 2-16 進制，字母大寫表示 10-15

總結

遞歸實現十進制轉二進制完美展示了「分治思想」與「調用棧隱式存儲」的結合。理解遞歸回溯時機對掌握樹遍歷、回溯算法、分治策略至關重要。實際工程中，位運算（num >> 1, num & 1）可替代除模運算提升性能。

1. 上一篇文章： Objective-C 協議詳解：@protocol 與委托模式實戰
2. 下一篇文章： 藍橋杯 C/C++ A組「振興中華」路徑計數：遞歸回溯全路徑枚舉

關於C語言

WPF/Silverlight 遊戲開發教程（三十之二）：施法距離判斷與魔法參數 XML 配置

右鍵點擊地圖 → 判斷主角與施放點距離是否在施法距離內 →

[你必須知道的.NET] 第三回：特性與屬性的歷史糾葛 (上)

引言 attribute 是 .NET Framework

折線分割平面：最大區域數計算與 C 語言實現

折線分割平面：最大區域數計算與 C 語言實現 經典的「直線

C語言輸出格式完全指南：printf 格式控制字符詳解

C語言輸出格式完全指南：printf 格式控制字符詳解 在