Question

写一个递归算法，用来把整数字符串转换为整数。例如： 43567 →43567。

Answer 1

【答案】：(1)思路
先递归调用本算法，以转换除去末位外剩余的字符串，结果乘以10；再转换末位。将两结果相加即为所求。
(2)算法
int stringToInt1(char*s,int start,int end){
/*把整数字符串s中从start到end的部分转换为整数*/
if(start＞end)return-1; /*转换失败*/
if(start==end)return s[end]-'0'; /*只有一个字符,直接转换*/
return stringToInt1(s,start,end-1)*10+s[end]-'0';
/*先转换其他位,再转换末位*/
}
int stringToInt(char*s){ /*把整数字符串s转换为整数*/
int i=0
while(s[i]!='\0')i++; /*计算字符串的长度*/
return stringToInt1(s,0,i-1);
}
(3)代价分析
设n为字符串的长度。该算法访问每个字符各一次，时间代价为O(n)，计算字符串的长度的时间代价也为O(n)。故总的时间代价为O(n)。
递归算法需要栈的支持，栈的大小与递归调用的深度成正比。所以实际空间开销为O(n)。