【思考题】字符串计算递归式

需求：

//已知一个递推公式A[N+1] = A[N] * 2 + 2，且A[1] = 2，求A[N]的值
//限制：
//0< n <65535
//举例：
//A[1] = 2, A[5] = 62, A[8] = 510

思路：

主要实现一个字符串加法计算函数，乘以2则可视为两个相同数相加而成。

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

char* string_add(char* s1, char* s2){
	int s1len,s2len,anslen;
	int k1,k2,ansk,c,s;
	char *ans,*ansrtn;

	s1len=strlen(s1);
	s2len=strlen(s2);

	anslen=s1len>s2len?s1len+1:s2len+1;
	ans = (char*)malloc(sizeof(char)*(anslen+1));
	k1 = s1len-1;
	k2 = s2len-1;
	ansk = anslen-1;
	s=0; c=0;
	while(k1>=0||k2>=0){
		if(k1>=0&&k2>=0){
			c = s1[k1--]+s2[k2--]-'0'-'0'+s;
			ans[ansk--] = c%10+'0';
			s = c/10;
		}
		else if(k1>=0){
			c = s1[k1--]-'0'+s;
			ans[ansk--] = c%10+'0';
			s = c/10;
		}
		else if(k2>=0){
			c = s2[k2--]-'0'+s;
			ans[ansk--] = c%10+'0';
			s = c/10;
		}
	}
	//free((char*)s1);
	ans[0] = s+'0';
	ans[anslen] = '';
	if(s==0){
		ansrtn = (char*)malloc(sizeof(char)*(anslen-1));
		strcpy(ansrtn, &ans[1]);
		free(ans);
		return ansrtn;
	}
	else
		return ans;
}

int main(void){
	int n,k;
	char *an, *temp;
	char *a1;

	a1 = (char*)malloc(sizeof(char)*2);
	a1[0] = '2'; a1[1] = '';
	scanf("%d", &n);
	if(n<1||n>65534)
		return 0;
	for(k=1, an=a1; k<n; k++){
		//temp = an;
		an = string_add(an, an);  //??????-->怎么释放掉之前的an指向的空间呀?
		//free(temp);
		//temp = an;
		an = string_add(an, "2");
		//free(temp);
	}

	printf("%s", an);

	system("pause");
	return 0;
}