递归（初识）

递归（初识）

注；本文文章代码来自与哔站郝冰老师，特在此声明

1 定义：一个函数自己直接或者间接调用自己（用栈来实现）

这边用两个实际例子举例

//  函数自己调用自己 
  #include
  void f(int n)
  {
  	if(n==1)
  	{
  		printf("哈哈哈！n");
	}
	else
	f(n-1);
  }
  int main(void)
  {
  	f(3);
  	return 0;
  }

2 

求阶乘
#include
long f(long n)
{
	if(n==1)
	return 1;
	else
	return f(n-1)*n; 
}
int main(void)
{
	printf("%ldn",f(5)); 
	return 0; 
}

求1-100之和
#include
int sum(long n)
{
	if(n==1)
	return 1;
	else
	return sum(n-1)+n; 
}
int main(void)
{
	printf("%d",sum(100));
	return 0;
}

2 函数调用

在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成过三件事

1将所有的实际参数，返回地址等信息传递给被调函数保存

2 为被调函数的局部变量（包括形参）分配存储空间

3 将控制转义到被调函数的入口

从被调函数返回主函数之前，系统完成的三件事：

1 保存被调函数的返回结果

2 释放背地哦啊函数的储存空间

3 依照被调函数保存返回地址将控制转移到调用函数

当有多个函数调用时，按照“后调用先返回”的·原则，上述函数之间的信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中·，没当调用一个函数时，就在栈顶分配一个存储区，进行压榨 *** 作，每当一个函数退出时，就是释放它的存储区，就是出栈从 *** 作，当前运行的函数永远都在栈顶位置

3 递归满足的三个条件

   1 递归必须得有一个明确的终止条件

   2该函数所处理的数据规模必须在递减

   4 这个转化必须是可解的