1、递归就是函数调用函数本身，运行起来就是函数嵌套函数，层层嵌套，所以函数调用、参数堆栈都是不小的开销，但是程序简单。
2、非递归就是不断地对参数入栈、出栈，省去了函数层层展开、层层调用的开销。虽然参数出入栈次数多了，但是一般都开辟固定的足够大的内存来一次性开辟、重复使用。
3、非递归是从堆栈的角度来编写程序，速度快，但代码复杂。
递归是从问题本身的逻辑角度来编写，虽然速度相对慢，但代码容易理解。
对于同一个问题，如果对速度要求不高，建议用递归方式。
- 递归和非递归分别实现求第n个斐波那契数。
- 递归和非递归分别实现strlen
- 递归和非递归分别实现求n的阶乘
- 递归实现n^k
- 递归方式实现打印一个整数的每一位
- 写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和（例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19 ）
- 编写一个函数 reverse_string(char * string)（递归实现）
实现：将参数字符串中的字符反向排列。
要求：不能使用C函数库中的字符串操作函数。
1.递归和非递归分别实现求第n个斐波那契数。
首先对于斐波那契数序列：1 1 2 3 5 8 13 21 34… 从第三项开始，每一项都等于前两项之和。
int count = 0; //计数计算多少次f1
int Fabonaci(int n) //递归
{
if (n == 1 || n == 2)
{
count++; //count计数，体会递归的耗时
return 1;
}
else
{
return Fabonaci(n - 1) + Fabonaci(n - 2); //第n个数的斐波那契等于前两个之和 问题不断化小
}
}
int main()
{
printf("%d\n", Fabonaci(5));
printf("计算%d次f1\n",count);
system("pause");
return 0;
}
int Fabonaci(int n) //非递归
{
int f1 = 1;
int f2 = 1;
int f3 = 0;
int i = 0;
for (i = 3; i <= n; i++)
{
f3 = f2 + f1; //1（f1） 1（f2） 2（f3） 3 5
f1 = f2;
f2 = f3; //1（f1） 2（f2） 3 （f3） 5
}
return f3;
}
int main()
{
printf("%d\n", Fabonaci(10));
system("pause");
return 0;
}
2.递归和非递归分别实现strlen
strlen遇到\0停止，引用数组引进头文件<string.h> ，字符串的长度就是字符个数。
#include<assert.h>
int count = 0;
int MyStrlen1(char *str) //非递归
{
//int count = 0;
assert(str != NULL); //断言str传进来不为空
while (*str != '\0')
{
count++;
str++;
}
return count;
}
int main()
{
char str[] = "abcdef";
printf("%s\n", str);
MyStrlen1(str);
printf("%d\n", count);
system("pause");
return 0;
}
int MyStrlen(char *str) //递归
{
if (*str == '\0')
{
return 0;
}
else
{
return 1 + MyStrlen(str + 1);
}
}
int main()
{
char str[] = "abcdef";// *str = "abcdef";
int len = MyStrlen(str);
printf("%d\n", len);
system("pause");
return 0;
}
3.递归和非递归分别实现求n的阶乘
int Fac(int n)//5! = 5*4! 5*4*3!
{
if (n == 1)
{
return 1;
}
else
{
return n*Fac(n - 1);
}
}
int main()
{
printf("%d", Fac(5));
system("pause");
return 0;
}
4.递归实现n^k
int MyPow(int n, int k) //递归
{
if (k == 0)
{
return 1;
}
else
{
return n*MyPow(n, k - 1); //n*n^k-1 = n^k
}
}
int main()
{
int res = MyPow(5,3);
printf("%d\n",res);
system("pause");
return 0;
}
5.递归方式实现打印一个整数的每一位
void print(int n) //123
{
if (n > 9)
{
print(n / 10);
}
printf("%d ", n % 10);
}
int main()
{
print(123);
system("pause");
return 0;
}
6 写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
int DigitSum(int n)
{
if (n < 10)
{
return n;
}
else//14 123
{
return DigitSum(n / 10) + n % 10;
}
}
int main()
{
int res = DigitSum(1729);
printf("%d\n",res);
system("pause");
return 0;
}
递归的过程是***先递后归*** 1729 172 17 1为递过程 ； 1 7 2 9为归过程
7.编写一个函数 reverse_string(char * string)（递归实现）
void reverse_string(char *p) //递归
{
int len = strlen(p); //不包括\0
char tmp = *p;
*p = *(p + len - 1);
*(p + len - 1) = '\0'; //保证字符串长度不变
if (strlen(p + 1) > 1)
{
reverse_string(p + 1);
}
*(p + len - 1) = tmp; // *p 和 *(p+len-1) 进行交换
}
int main()
{
char str[] = "abcdef";
printf("%s\n", str);
reverse_string(str);
printf("%s\n", str);
system("pause");
return 0;
}
void reverse_string(char *str) //非递归
{
char *left = str;
char *right = str + strlen(str) - 1;
while (left < right)
{
char tmp = *left;
*left = *right;
*right = tmp; //交换
left++;
right--;
}
}
int main()
{
char str[] = "abcdef";
printf("%s\n", str);
reverse_string(str);
printf("%s\n", str);
system("pause");
return 0;
}
