C語言遞歸求非負整數各位數字之和

C語言遞歸求非負整數各位數字之和

經典遞歸練習：輸入非負整數 n，返回各位數字之和。如 1729 → 1+7+2+9=19。

遞歸關係

DigitSum(n) = n%10 + DigitSum(n/10)，基線條件 n==0 → 0。

代碼實現

#include <stdio.h>

int DigitSum(unsigned int n) {
    if (n == 0) return 0;
    return n % 10 + DigitSum(n / 10);
}

int main() {
    unsigned int n;
    printf("請輸入非負整數：");
    scanf("%u", &n);
    printf("各位數字之和：%d\n", DigitSum(n));
    return 0;
}

運行示例

請輸入非負整數：1729
各位數字之和：19

遞歸執行過程追蹤 (1729)

DigitSum(1729)
= 9 + DigitSum(172)
= 9 + 2 + DigitSum(17)
= 9 + 2 + 7 + DigitSum(1)
= 9 + 2 + 7 + 1 + DigitSum(0)
= 9 + 2 + 7 + 1 + 0
= 19

迭代版本對比

int DigitSum_iter(unsigned int n) {
    int sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

迭代版 O(1) 空間，遞歸版 O(log n) 棧空間。數據範圍內兩者均可接受。

擴展：支持負數