100 Days of Code-day21

运用递归的设计思想编写一个递归版本的itoa函数。即通过递归调用把整数转换为字符串。

在采用递归方法时，我们可以直接按照整数最高位到最低位的顺序，将整数的每一位放入字符串数组中。也就是说不需要再通过反转字符串来得到最终结果。
如下图所示，为了先获得最高位，这里通过不断对数字进行取整操作直到结果为0。

那么在这个过程中就会出现一个问题，在不断对函数进行递归调用的过程中，我们会不会丢失了局部变量（比如形参）。
计算机告诉我们：不会！！！
原因：递归调用会使用系统提供的堆栈空间。遇到递归语句时就开始递归调用自身，如下面程序段所示。

if (n / 10)itoa(n / 10, num);//递归语句

如图1所示，当第一次调用时，为了防止丢失掉相关信息（局部变量以及程序被暂时终止（或者说是被打断）的位置），系统先将它们压入堆栈，起到保存这些信息的作用。
随后便将参数123传入第二次调用。以此类推，不断地将每次函数中变量的信息压入到堆栈中。直到n/10=0时不在继续进行入栈操作。此时程序可以正常进行。也就是下面所示的程序块。

else{i = 0;if (n < 0){num[i++] = '-';}}num[i++] = abs(n) % 10 + '0';num[i] = '\0';

这段程序执行结束后，得到了字符串数组num=“1”。接着程序自动返回到上一层函数的执行被打断的位置，继续执行后续程序。以此类推，不断进行出栈操作，直到堆栈为空。
图1
初始版本相对于改进版本的不足时，下面这段程序

intsign =0;if (n < 0){sign = -1;n = -n;}if (sign < 0)num[i++] = '-';

在初始版本中，每次进行入栈操作的时候都需要判断n和sign是否小于0。而后者只需要在最高位要被放入字符串数组之前判断n是否小于0即可。

初始版本：

#define MaxSize 100void itoa(int n,char num[]){static int i = 0;intsign =0;if (n < 0){sign = -1;n = -n;}if (sign < 0)num[i++] = '-';if(n/10)itoa(n/10,num);num[i++] = n % 10 + '0';num[i] = '\0';}int main(){int number = 1234;int i = 0;char num[MaxSize];itoa(number, num);printf("%s", num);return 0;}

改进版本：

#define MaxSize 100void itoa(int n,char num[]){static int i ;if (n / 10)itoa(n / 10, num);else{i = 0;if (n < 0){num[i++] = '-';}}num[i++] = abs(n) % 10 + '0';num[i] = '\0';}int main(){int number = 1234;int i = 0;char num[MaxSize];itoa(number, num);printf("%s", num);return 0;}