（七）函数递归
1.什么是递归？
程序调用自身的编程技巧；
过程或函数在其定义或说明中有直接或间接调用自身的一种方法，把大型复杂问题转化为一个与原问题相似的规模较小的问题来求解；
主要在于：把大事化小
最简单的递归：
#include<stdio.h>
int main()
{
printf("666\n");
main();
return 0;
}
为什么会出错？
注：
栈区——局部变量，函数形参
堆区——动态开辟的内存
静态区——全局变量，static修饰的变量
在运行中栈区一直在为666申请空间，当其占满后，便会stack overflow。
（https://stackoverflow.com/相当于程序员的知乎）
2.必要条件
存在限制条件，当满足这个条件的时候，递归便不再继续；
每次调用之后越来越接近这个限制。
3.练习
3.1接受一个无符号整形值，按顺序打印它的每一位
#include<stdio.h>
void print(int num)
{
if (num > 9)
{
print(num / 10);
}
printf("%d ", num % 10);
}
int main()
{
unsigned int num=0;
scanf("%d", &num);//num=1234
print(num);
//print(1234)
//print(123) 4
//print(12) 3 4
//print(1) 2 3 4
//每次剥一位，大事化小。
return 0;
}
3.2编写函数不允许创建临时变量，求字符串长度。
#include<stdio.h>
//#include<string.h>
int my_strlen(char* str)
{
int count = 0;
while(*str != '\0')
{
count++;
str++;
}
return count;
}
int main()
{
char arr[] = "bit";
//int ret = strlen(arr);
int len = my_strlen(arr);//数组传参传的是首元素的地址,所以函数不好用sizeof
printf("%d", len);
return 0;
}
不符合题意，创建了count变量；
//大事化小
//my_strlen("bit")
//1+my_strlen("it")
//1+1+my_strlen("t")
//1+1+1+my_strlen("")
//1+1+1+0
//3
#include<stdio.h>
int my_strlen(char* str)
{
if (*str != '\0')
return 1 + my_strlen(str + 1);
else
return 0;
}
int main()
{
char arr[] = "bit";
int len = my_strlen(arr);
printf("%d", len);
return 0;
}
（八）递归与迭代
迭代的思路是重复的去做一件事情。
1.求n的阶乘
循环
#include<stdio.h>
int Facl(int n)
{
int i = 0;
for(i = n-1; i >0; i--)
{
n = n * i;
}
return n;
}
int main()
{
int n = 0;
scanf("%d",&n);
int ret = Facl(n);
printf("%d\n", ret);
return 0;
}
递归
#include<stdio.h>
int Facl(int n)
{
if (n <= 1)
return 1;
else
return n = n * Facl(n - 1);
return n;
}
int main()
{
int n = 0;
scanf("%d",&n);
int ret = Facl(n);
printf("%d\n", ret);
return 0;
}
2.求第n个斐波那契数列
#include<stdio.h>
int Fib(int a)
{
if (a <= 2)
return 1;
else
return Fib(a - 1) + Fib(a - 2);
}
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
ret = Fib(n);
printf("%d", ret);
return 0;
}
该程序可以找出斐波那契数，可是当n=50时，笔者的电脑要花7分钟左右才能输出结果，说明程序效率较低。
计算过程如下：
50
49 48
48 47 47 46
47 46 46 45 46 46 45 44
...........
#include<stdio.h>
int count = 0;
int Fib(int a)
{
if (a == 3) //求第三个斐波那契数的次数
{
count++;
}
if (a <= 2)
return 1;
else
return Fib(a - 1) + Fib(a - 2);
}
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
ret = Fib(n);
printf("%d\n", ret);
printf("count=%d\n", count);
return 0;
}
通过计数器，我们发现求第40个斐波那契数时，第3个斐波那契数被重复运算了三千九百多万次，足以看到程序的低效。
所以，不是所以东西都适合用递归
这里我们尝试使用循环
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
ret = Fib(n);
printf("%d\n", ret);
return 0;
}
//结果可能错（产生溢出），但速度一定快
注：递归有时即使满足条件，也会栈溢出。
如：
#include<stdio.h>
void test(int n)
{
if (n < 10000)
{
test(n + 1);
}
}
int main()
{
test(1);
return 0;
}
自主研究：汉诺塔，青蛙跳台阶。