//根据下面递归函数：调用函数Fun(2)，返回值是多少（ ）
int Fun(int n)
{
if(n==5)
return 2;
else
return 2*Fun(n+1);
}
Fun(2)--->返回16
return 2*Fun(3) 2*8=16
|__Fun(3):8
return 2*Fun(4) 2*4=8
|__Fun(4):4
return 2*Fun(5) 2*2=4
|__Fun(5):2
return 2
//递归方式实现打印一个整数的每一位
#include<stdio.h>
void print(int n)
{
if (n > 9)
{
print(n / 10);
}
printf("%d ", n % 10);
}
int main()
{
int num = 0;
scanf("%d", &num);
print(num);
return 0;
}
?
//递归和非递归分别实现求n的阶乘（不考虑溢出的问题）
#include<stdio.h>
int func(int i)
{
if (i < 2)
{
return 1;
}
else
{
return i * func(i - 1);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = func(n);
printf("%d", ret);
return 0;
}
#include<stdio.h>
int main()
{
int n = 0;
scanf("%d", &n);
int sum = 1;
int i = 1;
for ( i = 1; i <= n; i++)
{
sum *= i;
}
printf("%d", sum);
return 0;
}
//递归和非递归分别实现strlen
#include<stdio.h>
//strlen的模拟（递归实现）
int func(char* arr)
{
if (*arr != '\0')
{
return 1 + func(arr + 1);
}
else
{
return 0;
}
}
int main()
{
char arr[] = "abcde";
int ret=func(arr);
printf("%d", ret);
return 0;
}?
#include<stdio.h>
#include<string.h>
int main()
{
char arr[] = "abcde";
int ret = strlen(arr);
printf("%d", ret);
return 0;
}
?strlen的含义是：求字符串中有效字符的长度，不包括\0
循环实现：
1. 给一个计数，用来统计有效字符的个数
2. 遍历字符串，只要没有遇到\0, 遇到一个字符给计数加1，直到遇到\0
//编写一个函数 reverse_string(char * string)（递归实现）
//实现：将参数字符串中的字符反向排列，不是逆序打印。
//要求：不能使用C函数库中的字符串操作函数。
#include<stdio.h>
void reverse_string(char* arr)
{
int len = strlen(arr);
char tmp = *arr;
*arr = *(arr + len - 1);
*(arr + len - 1) = '\0';
if (strlen(arr + 1) >= 2)
reverse_string(arr + 1);
*(arr + len - 1) = tmp;
}
int main()
{
char arr[] = "abcde";
reverse_string(arr);
printf("%s", arr);
return 0;
}
?
| 思路： |
| 逆置字符串，循环的方式实现非常简单 |
| ? 1. 给两个指针，left放在字符串左侧，right放在最后一个有效字符位置 |
| ? 2. 交换两个指针位置上的字符 |
| ? 3. left指针往后走，right指针往前走，只要两个指针没有相遇，继续2，两个指针相遇后，逆置结束 |
| */ |
| void reverse_string(char* arr) |
| { |
| char *left = arr; |
| char *right = arr+strlen(arr)-1; |
| while(left<right) |
| { |
| char tmp = *left; |
| *left = *right; |
| *right = tmp; |
| left++; |
| right--; |
| } |
| } |
| /* |
| 递归方式： |
| 对于字符串“abcdefg”，递归实现的大概原理： |
| ? 1. 交换a和g， |
| ? 2. 以递归的方式逆置源字符串的剩余部分，剩余部分可以看成一个有效的字符串，再以类似的方式逆置 |
| */ |
| void reverse_string(char* arr) |
| { |
| int len = strlen(arr); |
| char tmp = *arr; |
| *arr = *(arr+len-1); |
| *(arr+len-1) = '\0'; |
| if(strlen(arr+1)>=2) |
| reverse_string(arr+1); |
| *(arr+len-1) = tmp; |
| } |
//写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
//例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19
//输入：1729，输出：19
#include<stdio.h>
int func(int a)
{
if (a > 9)
{
return a%10+func(a / 10);
}
else
{
return a;
}
}
int main()
{
unsigned int a = 0;
scanf("%d", &a);
int ret = func(a);
printf("%d", ret);
return 0;
}
//编写一个函数实现n的k次方，使用递归实现。
#include<stdio.h>
int func(int a, int b)
{
if (b == 0)
return 1;
else if (b >= 1)
{
return a * func(a, b - 1);
}
}
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int ret = func(a, b);
printf("%d", ret);
return 0;
}?
?
//递归和非递归分别实现求第n个斐波那契数
#include<stdio.h>
int func(int n)
{
if (n <= 2)
{
return 1;
}
else
{
return func(n-1) + func(n - 2);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = func(n);
printf("%d", ret);
return 0;
}
#include<stdio.h>
int fib(int n)
{
int result;
int pre_result;
int next_older_result;
result = pre_result = 1;
while (n > 2)
{
n -= 1;
next_older_result = pre_result;
pre_result = result;
result = pre_result + next_older_result;
}
return result;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = fib(n);
printf("%d", ret);
return 0;
}?
?