练习（递归）

练1.根据下面递归函数: 调用函数Fun(2),求 返回值
int Fun(int n)
{
if (n == 5)
return 2;
else
return 2 * Fun(n + 1);
}

int main()
{
int ret = Fun(2);
printf("%d\n", ret);
return 0;
}

练2.字符串逆序（递归实现）
编写一个函数 reverse_string(char *string)（递归实现）
实现: 将参数字符串中的字符反向排列, 不是逆序打印。
要求: 不能使用C函数库中的字符串操作函数。
比如:
char arr[] = "abcdef";
逆序之后数组的内容变成: fedcba
int my_strlen(char* str)
{
int count = 0;
while (*str != '\0')
{
count++;
str++;
}
return count;
}

void reverse(char* str)
{
char tmp = *str;//1
int len = my_strlen(str);
*str = *(str + len - 1);//2
*(str+len - 1) = '\0';//3
if(my_strlen(str+1)>=2)
reverse(str+1);//4
*(str + len - 1) = tmp;
}
int main()
{
char arr[] = "abcdef";//[a b c d e f \0]
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz-2;
while (left<right)
{
char tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
}

printf("%s\n", arr);

return 0;
}
或者
void reverse(char arr[], int left, int right)
{
char tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
if(left<right)
reverse(arr, left+1, right-1);
}

int main()
{
char arr[] = "abcdefg";//[a b c d e f \0]
int left = 0;
int right = my_strlen(arr)-1;
reverse(arr, left, right);
printf("%s\n", arr);

return 0;
}

练3.计算一个数的每位之和（递归实现）
题目内容:
写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19
输入: 1729，输出: 19
int DigitSum(unsigned int n)//1234
{
if (n > 9)
return DigitSum(n / 10) + n % 10;
else
return n;
}

int main()
{
unsigned int n = 0;
scanf("%u", &n);
int sum = DigitSum(n);
printf("%d\n", sum);

return 0;
}

练4.递归实现n的k次方
题目内容:
编写一个函数实现n的k次方，使用递归实现。
Pow(n,k)
├─ k>0, n*Pow(n, k-1)
├─ k == 0, 1
└─ k<0, 1.0/Pow(n, -k);
double Pow(int n, int k)
{
if (k > 0)
return n * Pow(n, k - 1);
else if (k == 0)
return 1;
else
return 1.0 / Pow(n, -k);
}

int main()
{
int n = 0;
int k = 0;
scanf("%d%d", &n, &k);
double ret = Pow(n, k);
printf("%lf\n", ret);

return 0;
}