递归
什么是递归
程序调用自身的编程技巧称为递归（ recursion）。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小
递归的两个必要条件
1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。
2.每次递归调用之后越来越接近这个限定条件。
例题，按顺序打印每一位，例如：输入：1234， 输出：1 2 3 4
void print(int n)
{
if (n > 9)
{
print(n / 10);
}
printf("%d ", n % 10);
}
int main()
{
unsigned int num = 0;
scanf("%u", &num);//递归----函数自己调用自己
print(num);//
return 0;
}
print 函数可以打印参数部分数字的每一位
这个函数最重要的两个条件
1.if（ n > 9)如果没有这个条件的限制，那么print将一直调用自己形成死递归
2.print( n / 10) 逼近函数跳出的条件
只有这两个条件递归才能停下来
写递归代码的时候注意：
1.不能死递归，要有跳出条件，每次递归接近跳出条件。
2.递归层次不能太深（会出现栈溢出）**
练习：编辑函数不允许创建临时变量，求字符串长度
//方法一
int my_strlen(char* str)
{
int count = 0;
while (*str != '\0')
{
count++;
str++;
}
return count;
}
int main()
{
char arr[] = "bit";
int ret = my_strlen(arr);//模拟实现strlen
printf("%d\n", ret);
return 0;
}
这里虽然能计算出数组的长度但是违背了题意创建了临时变量count
//方法二
int my_strlen(char* str)
{
if (*str != '\0')
return 1 + my_strlen(str + 1);//调用三次
else
return 0;
}
int main()
{
char arr[] = "bit";
int ret = my_strlen(arr);//模拟实现strlen
printf("%d\n", ret);
return 0;
}
迭代和递归
例：求n的阶乘
方法一：迭代
int main()
{
int n = 0;
scanf("%d", &n);
int ret = 1;
for (int i = 1; i <= n; i++)
{
ret = ret * i;
}
printf("%d ", ret);
return 0;
}
方法二：递归
int Fac(int n)
{
if (n <= 1)
return 1;
else
return n * Fac(n - 1);
}
int main()
{
int n = 0;
scanf("%d",&n);
int ret = Fac(n);
printf("%d", ret);
return 0;
}
斐波那契数
//方法一：递归
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
斐波那契数:1 1 2 3 5 8 13 21 34 55…前两个数相加等于后面那个数
递归方法求解斐波那契数效率低,会出现栈溢出的现象。
可以使用循环的方法去求解
//循环的方式求斐波那契数效率高。
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 0;
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
循环方法：a + b = c; 每次计算都记录，不会出现大量计算