在《C程序設計語言》（K&R）一書的遞歸章節中，留有一個練習：使用遞歸實現 itoa 函數，將整數轉換為字符串。書中給出的迭代版本會產生逆序字符串，最後需要調用 reverse 反轉；而遞歸版本天然避免了這個問題。然而，初學者嘗試用一級指針 char *s 實現時，往往會遇到「只能輸出最高位和最低位」的離奇現象。本文將深入剖析錯誤根因，並給出基於二級指針 char **s 的正確實現方案。
直觀的想法是：在遞歸調用時傳入 s++，讓指針隨著遞歸深度向後移動，最後在回溯階段填入字符。代碼如下：
void itoa(int n, char* s) {
if (n < 0) {
*s = '-';
s++;
}
if (abs(n) / 10)
itoa(abs(n) / 10, s++);
*s = abs(n) % 10 + '0';
}
編譯運行後發現，輸入 12345 只能得到類似 "15" 的結果——首尾兩位數字，中間全丟失。
C 語言函數參數傳遞採用值傳遞。當調用 itoa(abs(n)/10, s++) 時，s++ 是後置自增，傳入遞歸調用的是 自增前的值（即當前 s 指向的地址）。更關鍵的是，每一層遞歸都擁有獨立的參數副本 s。在深層遞歸中對 s 的自增操作（s++），只修改了當前棧幀的局部副本，無法回傳給上一層調用者。
具體過程：
itoa(12345, s)，s 指向數組首地址。1，此時最深層的 s 仍指向首地址（因為每層傳入的都是自增前的值），寫入 '1'。s 從未被修改，依然指向首地址，但首地址已被佔用，首層執行 *s = '5' 時，實際寫入的是 s[1]（因為首層代碼開頭有 s++？實際上首層沒有自增，這裡需結合負號處理細分，但核心結論不變：指針位移未在調用鏈中傳遞）。結果：只有最高位（最深層寫入首地址）和最低位（首層寫入次地址）被保留，中間位數字丟失在各層棧幀的獨立指針副本中。
要讓遞歸各層共享同一個指針變量，必須傳遞 指針的地址，即 char **s。這樣各層通過解引用 *s 訪問並修改同一個 char * 變量，指針位移對所有層級可見。
#include <stdlib.h> // abs()
void itoa(int num, char** s) {
if (num < 0) {
**s = '-';
(*s)++;
}
if (abs(num / 10) > 0) {
itoa(abs(num / 10), s);
(*s)++; // 遞歸返回後，移動指針留位給當前位
}
**s = abs(num % 10) + '0';
}
char **s：接收 char * 變量的地址，實現多層共享同一指針變量。abs(num / 10) > 0：遞歸終止條件，處理完最高位後停止深入。itoa(abs(num / 10), s)：直接傳遞 s（二級指針），不做自增，保證各層操作同一指針變量。(*s)++ 在遞歸返回後執行：關鍵！先遞歸處理高位，返回後再移動指針，為當前位騰出位置。這與迭代版「先取低位再反轉」的邏輯恰好相反，遞歸利用棧的「後進先出」天然實現了正序輸出。abs() 處理負數：避免 INT_MIN 取絕對值溢出（abs(INT_MIN) 未定義行為），實際工程中需額外處理 INT_MIN 特例，此處為演示核心邏輯。int main() {
char buf[100];
char *p = buf;
itoa(12345, &p);
*++p = '\0'; // 手動添加結束符
printf("正數: %s\n", buf); // 輸出: 12345
p = buf;
itoa(-2147483647, &p); // 32位系統最大負數(不含INT_MIN)
*++p = '\0';
printf("負數: %s\n", buf); // 輸出: -2147483647
return 0;
}
| 方案 | 核心機制 | 結果 |
|---|---|---|
一級指針 char *s + s++ | 值傳遞，各層指針副本獨立，位移不回傳 | 失敗，僅保留首尾字符 |
二級指針 char **s + 遞歸後 (*s)++ | 傳址調用，各層共享同一指針變量，位移全局可見 | 成功，正序輸出完整字符串 |
核心心法：遞歸中若需修改調用者可見的指針位置，必須傳遞指針的指針（二級指針）。這不僅適用於 itoa，也是處理鏈表頭插法、字符串構建等「指針位移需回傳」場景的通用模式。
