目录
递归就是一个函数在它的函数体内调用它自身来解决问题,实现将大事化小,复杂化简单
执行递归函数,满足递归关系将反复调用其自身,每调用一次就进入新的一层(类似递推的感觉)
如果函数一直递推,每递推一次就会开辟一个空间,而内存是有限的 就需要一个限制条件,当无法满足继续递归时,就开始返回(回归)
注:因为开辟空间,返回时调用函数中的变量依然会保持使用,以此实现反向输出得到想要的结果
递归的精髓在于通过不断地重复逼近一个最终的结果,它更多的是一种思想,用于解决某些问题
举例打印1234,尝试分解问题,逼近想要的结果
一个数余10,我们可以得到个位数 想的到十位数,可以先除十再余十(整形间除法是没有小数位的)
void print(unsigned int n)
{
if (n > 9)
{
print(n / 10);//递推关系
}
printf("%d ", n % 10);//开始返回
}
int main()
{
//接受一个整型值(无符号),按照顺序打印它的每一位
unsigned int num = 0;
scanf("%u", &num);//1234
print(num);
return 0;
}
这样看来递归还是非常有意思的哈
找到递归关系:想特点,字符串是以‘\0’结尾的
参考代码
int my_strlen(char* s)
{
if (*s != '\0')
{
return 1 + my_strlen(s+1);
}
else
{
return 0;
}
}
int main()
{
//求字符串长度
char arr[10] = "abcd";
//数组名arr是数组首元素的地址 - char*
int len = my_strlen(arr);//6
printf("%d\n", len);
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);//3
//去n的阶乘
int ret = Fac(n);
printf("%d\n", ret);
return 0;
}
递归这样看来十分快捷简便,但它也有局限,毕竟递归是一个不断调用函数重复的过程
0, 1, 1, 2, 3, 5, 8, 13, 21, ··· 斐波那契数列是一个从第三项开始,每一项都等于前两项之和的数列问题
int count = 0;
int Fib1(int n)
{
if (n == 3)
{
count++;
}
if (n <= 2)
return 1;
else
return Fib1(n - 1) + Fib1(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
// printf("count = %d\n", count);
return 0;
}
仅从求第五项来看,就调用了4次第一项 想想那第五十项,又要调用多少次,计算有需要多久呢?(存在明显问题)
而用循环对于这个问题却又变得简单许多,至少计算很快
//迭代(循环)
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;
}
1. 简洁
2.在树的前序,中序,后序遍历算法中,递归的实现明显要比循环简单得多。
1.递归由于是函数调用自身,而函数调用是有时间和空间的消耗的:每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间。->效率
2.递归中很多计算都是重复的,由于其本质是把一个问题分解成两个或者多个小问题,多个小问题存在相互重叠的部分,则存在重复计算,如fibonacci斐波那契数列的递归实现。->效率
3.调用栈可能会溢出,其实每一次函数调用会在内存栈中分配空间,而每个进程的栈的容量是有限的,当调用的层次太多时,就会超出栈的容量,从而导致栈溢出。->性能