c语⾔经典-递归
说到递归，相信⼤家都不陌⽣，采⽤递归可以解决⼀些重复性，相似性⾼的东西。今天我就介绍⼀些经典递归问题斐波那契数列
#include<stdio.h>
#include<stdlib.h>
int fib(int n)
{
if (n <= 0)//判断错误情况
return 0;
else if (n <= 2)//判断1-2的情况
return 1;
else
{
return fib(n - 1) + fib(n - 2);
}
}
//⾮递归求法
int fib1(int n)
{
if (n <= 0)//判断错误情况
return 0;
else if (n <= 2)//判断1-2的情况
return 1;
else
{
int i = 1, j = 1, k = 1;
int sum = 0;
for (k = 3; k <= n; k++)
{
sum = i + j;
i = j;
j = sum;
}
return sum;
}
}
int main()
{
//1 1 2 3 5 8 13 21 34 55
int value = 0;
int sum = 0;
printf("请输⼊>");
scanf_s("%d", &value);
puts("递归求法:");
sum = fib(value);
printf("sum = %d\n", sum);
puts("⾮递归求法:");
sum = fib1(value);
printf("sum = %d\n", sum);
system("pause");
return 0;
}
斐波那契数列的规律是1 1 2 3 5 8 13 21 34 55，第三项后每⼀项都是前两项之和，第n项的前n项和等于第n+2项值-1。
对于这样的问题，在编程中我们可以采⽤for循环和递归，for循环中我们分别⽤两个变i,j量分别指向1 1,sum = i+j，循环⼀次我们移项。i =j;
j = sum；就这样循环n-2项就可以求出第n项的值。递归的更为简单，看代码就可以理解。
但是在这⾥，我提⼀下，斐波那契数列虽然⽤递归表达简单，但是它的运⾏效率⽐for()低，如果要求的话，采⽤for()更好，递归仅作为了解。
2、写⼀个递归函数DigitSum(n)，输⼊⼀个⾮负整数，返回组成它的数字之和，如1729 1+7+2+9
#include<stdio.h>
#include<stdlib.h>
int DigitSum(int n)
{
if (n)
{
//DigitSum(n / 10);
return n % 10 + DigitSum(n / 10);
}
return 0;
}
int main()
{
int value = 0;
递归函数c语言规则int sum = 0;
printf("请输⼊⼀个⾮负整数>");
scanf_s("%d", &value);
sum = DigitSum(value);
printf("sum = %d\n", sum);
system("pause");
return 0;
}
这个没什么说的，就是递归的基本⽤法。在递归中，每个递归都有⼀个共同的特点，就是每次递归都会趋近递归结束条件。
3、编写⼀个函数 reverse_string(char * string)（递归实现）
实现：将参数字符串中的字符反向排列。
要求：不能使⽤C函数库中的字符串操作函数。
#include<string.h>
int My_strlen(char* s)
{
if (*s != '\0')
{
return 1 + My_strlen(s + 1);
}
return 0;
}
void reverse_string(char * str)
{
int len = mystrlen(str);//获得字符长度，不包括\0
char tmp;
if (*str)
{
tmp = str[0];
str[0] = str[len - 1];
str[len - 1] = 0;
reverse_string(str + 1);
str[len - 1] = tmp;
}
}
int main()
{
char str[20] = "abcdefg";
puts(str);
reverse_string(str);
puts(str);
system("pause");
return 0;
}
这道题应该是递归中特难的了，字符串的逆序，⾥⾯的递归在纸上写⼀下它的递归过程。它的每⼀步都很精巧，不多不少。这道题希望⼤家好好品⼀下，
4、递归⽅式实现打印⼀个整数的每⼀位
void Print(int n)
{
//1729
//(172) 9
//(17) 2 9
//(1) 7 2 9
if(n > 9)
{
Print(n / 10);
}
printf("%d ",n % 10);
}
int main()
{
int value = 0;
printf("请输⼊>");
scanf_s("%d", &value);
Print(value);
system("pause");
return 0;
}
这道题采⽤递归最完美不过了，1729求每位数从后往前容易，从前往后就不容易了。值得品味！
5、编写⼀个函数实现n^k，使⽤递归实现
double Calculate_power(int value, int power)
{
//power位为传递进来的次⽅，有三种情况- 0 +
if (power < 0)
{
if (power == -1)
return 1.0 / value;
return  1.0 / value * Calculate_power(value, power + 1); }
else if (power == 0)
{
return 0.0;
}
else
{
if (power == 1)
return value * 1.0;
return 1.0 * value * Calculate_power(value, power - 1); }
}
int main()
{
int value = 0, power = 0;
double acc_value = 0.0;
printf("请输⼊您想计算的值和多少次⽅value、power>"); scanf_s("%d%d", &value, &power);
acc_value = Calculate_power(value, power);
printf("acc_value = %f\n", acc_value);
system("pause");
return 0;
}
我写的这个可以求负数的n次⽅，⼤家可以看⼀下。汉诺塔
经典汉诺塔问题，往年⾯试的经典问题之⼀

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。