【C语言初阶】函数学习报告

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 函数知识板块
• 一、函数是什么？C语言中的函数分类
• 二、库函数的查找网站
• 三、自定义函数中的传值和传址调用的区别
• 四、函数练习（4个）
• • 1.写一个函数可以判断一个数是不是素数。
  • 2.写一个函数判断一年是不是闰年。
  • 3.写一个函数，实现一个整形有序数组的二分查找。
  • 4.写一个函数，每调用一次这个函数，就会将 num 的值增加1。
• 五、延伸知识：bool类型
• 六、函数的嵌套调用和链式访问
• • 1.函数调用
  • 2.链式访问
• 一些函数的错误写法，延伸 : mian函数的三个参数
• • 1、一些函数错误写法
  • 2、mian函数的三个参数
• 七、函数的声明与定义，延伸 ：函数模块化，函数生成静态库
• • 1.函数的声明与定义
  • 2.函数模块化，利于协作
  • 3、函数编译成静态库
• 函数递归详解 —— 练习1，练习2（画图讲解）
• • 练习1：（画图讲解）
  • 练习2：（画图讲解）
• 递归与迭代 —— 练习3，练习4 ，延伸：栈溢出
• • 练习3
  • 练习4

---

函数知识板块

下面我把我函数所学的内容到的内容大致归下面9个板块，方便我们对函数学习的总结，当然如有错误和遗漏望指出，谢谢！接下来我会在后面的内容中一一去讲述这几个板块，让我们往下看吧

• 库函数的搜索网站
• 自定义函数中的传值和传址调用的区别
• 函数练习（4个）
• 延伸知识：bool类型
• 函数的嵌套调用和链式访问
• 一些函数的错误写法，延伸 : mian函数的三个参数，
• 函数的声明与定义，延伸 ：函数模块化，函数生成静态库
• 递归 —— 练习1，练习2
• 递归与迭代 —— 练习3，练习4 ，延伸：栈溢出

一、函数是什么？C语言中的函数分类

讲板块前咱们得科普一下官方的知识是吧，函数是什么？函数的分类？简单了解一下

官方的回答：数学中我们常见到函数的概念。但是你了解C语言中的函数吗？
维基百科中对函数的定义：子程序

• 在计算机科学中，子程序（英语：Subroutine, procedure, function, routine, method,
  subprogram, callable unit），是一个大型程序中的某部分代码， 由一个或多个语句块组
  成。它负责完成某项特定任务，而且相较于其他代码，具备相对的独立性。
• 一般会有输入参数并有返回值，提供对过程的封装和细节的隐藏。这些代码通常被集成为软
  件库。

函数的分类：函数分库函数和自定义函数

• 库函数：c语言本身就有的，是c语言的语法统一的，比如：scanf、printf 输入输出函数等等，这些函数都有着特定的功能，c语法规定好的，库函数有 IO函数；字符串操作函数； 字符操作函数；内存操作函数；时间/日期函数；数学函数；其他库函数 这几类
• 自定义函数：自己写的函数就叫自定义函数，自定义函数和库函数一样，有函数名，返回值类型和函数参数。

二、库函数的查找网站

下面这个网站是c++官方网站，里面都有你想要的了解的库函数相关的介绍及使用,家人们赶紧收藏起来吧：

http://cplusplus.com
http://en.cppreference.com（英文版）
http://zh.cppreference.com（中文版）

用法：
1.比如我在第一个网站搜 strcpy这个库函数

上面我标了搜索出来的strcoy的介绍内容板块，是不是看到这个界面英语就晕，老实说我也晕，因为我不会英语，没关系像我们这种菜鸡可以使用edge的页面翻译或者有道翻译，但这治标不治本，以后如果我们要深入编程，就必须会英语因为有时候翻译器会翻车，看懂上面的介绍那我们就把strcop搬到vs编译器下使用吧

---

2. 再来查一个：menset

vs2019 编译器下使用

---

三、自定义函数中的传值和传址调用的区别

传值调用

函数的形参和实参分别占有不同内存块，对形参的修改不会影响实参。

传址调用

1. 传址调用是把函数外部创建变量的内存地址传递给函数参数的一种调用函数的方式。
2. 这种传参方式可以让函数和函数外边的变量建立起真正的联系，也就是函数内部可以直接操作函数外部的变量。

• 传值调用和传址调用是什么？
• 什么时候用传值调用和传址调用？

带着上面两个问题我们来探讨一下这下面这两个函数的区别，分别是加法函数（传值调用），和交换函数（传址调用）

1. 加法函数

2. 交换函数（把两个值进行交换）

我们想一下我们怎么把两个数进行交换呢，假设我们有一瓶酱油x，一瓶饮料y，那我们怎么将他们两个液体对调进行交换呢？这是可以找一个空瓶子z，把酱油x倒给z，把饮料y倒给x，再把z中的酱油倒给此时空瓶y不就可以了。

图示：

代码：


错误版本和正确版本解析区别：

错误版本用的就是传值调用，而正确版本用的是传址调用，
为什么在加法函数上传值调用可以，而交换函数上行不通呢，

因为交换函数需要改变实参a和b的值，所以传值调用上是行不通的，因为传值调用就是把实参a和b的值传给形参x，y，但不会改变实参a和b，形参只是实参的一份临时拷贝，对形参的修改影响不了实参，形参会创建自己的空间地址，而加法函数不需要改变实参的值，只需要a和b内容传给函数即可。

而传址调用本质上是传递地址，与传值调用传递内容不同，*x 和 *y 通过地址找到地址里的内容进行修改，本质上就是在修改实参

结论：当我们如果要对实参的内容进行修改时就必须使用传址调用，反之，如果只需要单单的实参传值的话则用传值调用

四、函数练习（4个）

• 写一个函数可以判断一个数是不是素数。
• 写一个函数判断一年是不是闰年。
• 写一个函数，实现一个整形有序数组的二分查找。
• 写一个函数，每调用一次这个函数，就会将 num 的值增加1。

1.写一个函数可以判断一个数是不是素数。

//素数是只能被1和他本身整除的数
//比如 7，他只能被1和7整除，也就是说除了2~6都不能整除7，
//所以当判断一个数是否为素数时，可以判断他是否被1和本身以外的数整除，是的话就不是素数
//7            
//1和7整除  
//2 3 4 5 6都不能整除7，则7是素数

//打印100~200之间的素数
#include
int main()
{
    int count = 0;//统计素数个数，定义的计数器
    
    //产生100~200的数
    int i = 0;
    for (i = 100; i <= 200; i++)
    {
        int flag = 1;// flag = 1，表示素数，让判断的每个数都可以试除到2~i-1的数
        
        //产生2 ~ i-1 的值
        int j = 0;
        for (j = 2; j <= i - 1; j++)
        {
            //判断是否被1和本身以外的数整除,如果被整除说明不是素数
            if (i % j == 0)
            {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
        {
            count++;//每一个是素数的加起来
            printf("%d ", i);//打印每一个素数
        }
    }
    printf("ncount = %dn", count);//打印素数个素
    return 0;
}

//提高效率方案，我们想我们是不是可以不用去试除2~i-1的数，还有100 ~ 200没有中的素数没有偶数
//
//比如 m 不是素数，
// m = a * b；
//16 = 2 * 8 或者 4 * 4 肯定可以写成这两种形式
//a和b中一定有一个数字是 <= sqrt(m)
// 
//sqrt是开平方，16开平方是不是4，相当于如果有哪个数被开方的数整除就肯定不是素数
//比如16肯定能被16开平方后的4整除所以16不是素数
//
//sqrt是数学库函数
//开平方
//math.h
#include
#include
int main()
{
    int count = 0;//统计素数个数
   
    int i = 0;
    //100 ~ 200没有中的素数没有偶数，这边把100改成101，i++改成i+=2，使每个数都奇数
    for (i = 101; i <= 200; i+=2)
    {
        int flag = 1;// flag = 1，表示素数，让判断的每个数都可以试除到2~i-1的数
        
        //产生2 ~ sqrt(i)的值,提高效率
        int j = 0;
        for (j = 2; j <= sqrt(i); j++)
        {
            //判断是否被1和本身以外的数整除
            if (i % j == 0)
            {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
        {
            count++;//每一个是素数的加起来
            printf("%d ", i);//打印每一个素数
        }
    }
    printf("ncount = %dn", count);//打印素数个素
    return 0;
}


//写一个函数可以判断一个数是不是素数。

#include
#include

//返回值是 1 则是素数,0 则不是素数
int is_prime(int n)//形参 n
{
	//产生2~sqrt(i)的值
	int j = 0;
	for (j = 2; j <= sqrt(n); j++)
	{
		//每一个传进来的值都去试除2~sqrt(i),被整除的话就不是素数，返回0
		if (n % j == 0)
		{
			return 0;
		}
	}
	return 1;//是素数，返回1
}
int main()
{
	//产生100 ~ 200的数,改成产生他们之间的奇数，因为100~200之间的素数没有偶数
	int count = 0;//统计素数个数
	int i = 0;
	for (i = 101; i <= 200; i+=2)
	{
		if (is_prime(i))//判断是不是素数，实参i
		{
			count++;
			printf("%d ", i);
		}
	}
	printf("ncount = %dn", count);
	return 0;
}

2.写一个函数判断一年是不是闰年。

//闰年判断的规则：
//1. 能被4整除，并且不能被100整除是闰年
//2. 能被400整除是闰年

//打印1000~2000年之间的闰年
#include
int main()
{
	//产生1000~2000的数
	int year = 0;
	for (year = 1000; year <= 2000; year++)
	{
		//判断
		if ((year % 4 == 0)&&(year % 100 != 0) || (year % 400 == 0))
		{
			printf("%d ", year);
		}
	}
	return 0;
}


//写一个函数判断一年是不是闰年
//是闰年返回1
//非闰年返回0
#include
int is_leap_year(int y)
{
	if ((y % 4 == 0) && (y % 100 != 0) || (y % 400 == 0))
		return 1;
	else
		return 0;
}
int main()
{
	//产生1000~2000的数
	int year = 0;
	for (year = 1000; year <= 2000; year++)
	{
		//判断
		if (is_leap_year(year))//判断是否闰年函数
		{
			printf("%d ", year);
		}
	}
	return 0;
}

3.写一个函数，实现一个整形有序数组的二分查找。

//写一个函数，实现一个整形有序数组的二分查找
#include
int binary_search(int arr[], int k, int sz)//二分查找实现
{
	int left = 0;
	int right = sz - 1;

	while (left <= right)
	{
		int mid = (left + right) / 2;//求中间元素mid要放在循环中，那样就可以让mid的值在变化中不断的去判断
									//如果放在外面mid值一直是5不会发生变化
		if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}

	return -1;
}
int main()
{
	//产生数组1~10
	int	arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	//查找的值7
	int k = 7;
	//元素数组个数sz
	int sz = sizeof(arr) / sizeof(arr[0]);
	//查找有序数组函数
	int ret = binary_search(arr, k, sz);//数组在传参的时候要写数组名
	//设置待会接收的返回值，
	//-1就是找不到，其他就是找的到
	if (ret == -1)
	{
		printf("找不到n");
	}
	else
	{
		printf("找到了，下标是：%dn", ret);
	}

	return 0;
}

//形参和实参名字可以相同也可以不同
// 数组传参时传递的是首元素的地址，而不是整个数组，所以不要再函数内部求数组元素个数
// 错误示范
#include
int binary_search(int arr[], int k)//形参arr看上去是数组，本质是指针变量
{
	
	int sz = sizeof(arr) / sizeof(arr[0]);//err,不要奢求在函数内部求数组元素个数
						 //因为如果在函数内部求得到的也只是首元素的个数大小4/4=1
	int left = 0;
	int right = sz - 1;
	

	while (left <= right)
	{
		
		int mid = (left + right) / 2;//求中间元素mid要放在循环中，那样就可以让mid的值在变化中不断的去判断
									//如果放在外面mid值一直是5不会发生变化
		if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}

	return -1;
}
int main()
{
	//产生数组1~10
	int	arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	//查找的值7
	int k = 7;
	
	//查找有序数组函数
	int ret = binary_search(arr, k);//数组在传参的时候要写数组名
	//设置待会接收的返回值，
	//-1就是找不到，其他就是找的到
	if (ret == -1)
	{
		printf("找不到n");
	}
	else
	{
		printf("找到了，下标是：%dn", ret);
	}
	return 0;
}

4.写一个函数，每调用一次这个函数，就会将 num 的值增加1。

//写一个函数，每调一次这个函数，就会将num的值增加1
#include
void add(int* p)
{
	(*p)++;
}
int main()
{
	int num = 0;
	add(&num);
	printf("%dn", num);//1
	add(&num);
	printf("%dn", num);//2
	add(&num);
	printf("%dn", num);//3
	add(&num);
	printf("%dn", num);//4
	return 0;
}

五、延伸知识：bool类型

bool类型是c99中新增的语法，就是用来表示真假，true 真，false 假。头文件是
在之前没有bool类型我们也照样写代码，bool类型一般不经常使用，但咱们也许在阅读代码的时候会遇到，所以浅浅了解一下，当我们要使用bool类型时一定要注意自己所使用的编译器是否支持，毕竟是新语法！

// bool类型，头文件，true 真，false 假
//
//例：用bool类型求素数
#include
#include
#include
bool is_prime(int n)
{ 
	int j = 0;
	for (j = 2; j <= sqrt(n); j++)
	{
		if (n % j == 0)
		{
			return false;//0
		}
	}
	return true;//1
}
int main()
{
	//产生100~200的数
	int i = 0;
	for (i = 100; i <= 200; i++)
	{
		if (is_prime(i))
		{
			printf("%d ", i);
		}
	}
	printf("n%d", sizeof(bool));//bool类型大小为 1
	return 0;
}

六、函数的嵌套调用和链式访问 1.函数调用

函数可以嵌套调用，但不能嵌套定义，函数都是独立、平等的

//嵌套调用
#include 
void new_line()
{
	printf("hehen");
}
void three_line()
{
	int i = 0;
	for (i = 0; i < 3; i++)
	{
		new_line();
	}
}
int main()
{
	three_line();//打印3个hehe
	return 0;
}


//函数可以嵌套调用，但不能嵌套定义
//
//嵌套定义 err
int add(int x, int y)
{
	return x + y;
	int sub(int x, int y)//err
	{
		return x - y;
	}
}
int main()
{
	return 0;
}

2.链式访问

把一个函数的返回值作为另外一个函数的参数

//链式访问
#include 
#include 
int main()
{
	char arr[20] = "hello";
	int ret = strlen(strcat(arr, "bit"));//这里介绍一下strlen函数
	printf("%dn", ret);
	return 0;
}

//理解下面这个链式访问题就差不多了
#include 
int main()
{
	//printf函数的返回值是打印的字符的个数
    //也就是先打印43,43是两位字符个数，第二个输出就打印2,2是1位字符个数，第一个输出就打印1
	//最后在屏幕上就是4321
	printf("%d", printf("%d", printf("%d", 43)));//4321
	
	return 0;
}

一些函数的错误写法，延伸 : mian函数的三个参数 1、一些函数错误写法

1.//当函数是void类型不需要返回值时，主函数在传参的时候就不要写返回值的函数类型了
void test()
{
	printf("hehen");
}
int main()
{
	int n = test();//err

	return 0;
}

2.//函数不写返回值的时候，默认返回类型是int
add(int x, int y)//不推荐的写法
{
	return x + y;
}
int main()
{
	int a = 10;
	int b = 20;
	int c = add(a, b);
	printf("%dn", c);

	return 0;
}


3.//写了int返回类型，函数内部就写一下返回值，不要写的模棱两可
int add(int x, int y)
{
	//没写返回值，不推荐
	printf("hehen");
	
}
//上面的代码在一些编译器上返回的是函数中执行过程中最后一条指令的执行结果
//最后语句是hehen,所以打印5
int main()
{
	int a = 10;
	int b = 20;
	int c = add(a, b);
	printf("%dn", c);

	return 0;
}


4.//明确的说明，main函数不需要参数
int main(void)
{
	return 0;
}

5.//当函数不需要返回值时，就不要给他传值了
void test()
{
	printf("hehen");
}
int main()
{
	test(100);//不推荐的
	test();
}

2、mian函数的三个参数

//本质上main函数是有参数的
//main函数有3个参数

int main(int argc, char* argx[], char* envp[])
{
	return 0;
}

---

七、函数的声明与定义，延伸 ：函数模块化，函数生成静态库 1.函数的声明与定义

函数声明：

• 告诉编译器有一个函数叫什么，参数是什么，返回类型是什么。但是具体是不是存在，函数
  声明决定不了。
• 函数的声明一般出现在函数的使用之前。要满足先声明后使用。
• 函数的声明一般要放在头文件.h中的。

函数定义：

函数的定义是指函数的具体实现，交待函数的功能实现。
函数定义一般放在源文件.c 中的

#include
//一、函数的声明与定义
//先声明后使用

//函数的声明
int add(int x, int y);

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);

	int sum = add(a, b);
	printf("%dn", sum);

	return 0;
}

//函数的定义：交代函数功能的实现
int add(int x, int y)
{
	return x + y;
}

2.函数模块化，利于协作

函数可以说是我们编程必不可少的一部分，当我们熟悉函数的写代码时，以后写代码基本就缺不了函数了
因为函数具有独立的功能，加上以后当我们步入公司必须多人协作时，总不可能很多人一起在一个.c文件写代码吧
模块化很好的使我们多人完成一个项目，比如写一个计算器，一个写加法，一个写减法等等，然后使用时直接调函数声明的头文件就好

函数声明放.h文件，函数定义放在.c 文件中
加法函数为例：

3、函数编译成静态库

当我们有能力时，写一个函数功能卖给别人时，只卖功能，出问题帮你维护代码
我们不可能把源文件.c给他，如果给的话就透露了代码，那他完全可以找个人代码复刻，然后直接就不给你这个函数功能续费了，这时我们就可以把函数编译成静态库和函数声明一起打包给人家，而静态库里面都是二进制的东西，他就看不懂了，可以很好的保护我们的代码隐私

这里以加法函数为例，假设卖给b公司，编译器：vs2019

• 函数生成静态库步骤

① 新建一个add.7.11的工程，此工程.h放函数声明，.c放函数定义（功能实现：加法）

② 将工程编译成静态库

③ 打开生成静态库文件的储存位置

• 当b公司拿到add.7.11.lib文件和函数声明add.h文件,使用步骤：
  
• 生成的静态库全部都是二进制的东西

用vs打开add.7.11.lib文件查看

函数递归详解 —— 练习1，练习2（画图讲解）

• 递归是什么？

程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的
一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
递归策略
只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小

• 递归的两个必要条件

1. 存在限制条件，当满足这个限制条件的时候，递归便不再继续。
2. 每次递归调用之后越来越接近这个限制条件。

练习1：（画图讲解）

接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1 2 3 4

• 非递归思路参考代码：

//%d 是打印有符号的整数(会有正负数)
//%u 是打印无符号的整数
 
//非递归的解法思路,
//但这种只能倒着输出4321，不符合题目要求，当然也可以一个一个输出然后排好位置，这个太麻烦
#include
int main()
{
	unsigned int num = 0;
	scanf("%u", &num);
	//非递归的解法思路:
	while(num)
	{
		printf("%u", num % 10);//1234 % 10 == 4
		num = num / 10;// 1234/10 == 123
	}
	return 0;
}

• 递归解法代码参考：

//递归解法
// 
//print(1234)
//print(123) 4  
//print(12) 3 4
//print(1) 2 3 4
//1 2 3 4
//
#include
void print(unsigned int n)
{
	if (n > 9)
	{
		print(n / 10);// 1234/10==123
	}
	printf("%u ",n % 10);// 1234%10==4
}
int main()
{
	unsigned int num = 0;
	scanf("%u", &num);//1234
	print(num);//接收一个整型值（无符号），按照顺序打印它的每一位。

	return 0;
}

（1）函数的两个必要条件和栈溢出。

如果当我们缺失条件中其中一个，就会导致栈溢出，每一次的函数调用都会在栈区上申请空间，栈区的空间又是有限的，而递归就是调用自身的，栈溢出的话就会出现死递归，程序崩溃，所以这两个条件非常重要必不可少

（2）函数递归的过程（画图）

画图能很好帮助我们理解递归的过程，在图中我们可以看到递归是函数在调用自身的写法，然后一直递，递到限制条件，不能递，然后开始归。要把递归两字拆开去理解它，我图画的比较潦草家人们一定要仔细看先看蓝线递，后看红线归，看图时可以结合我上面代码注解，可以更好理解

练习2：（画图讲解）

编写函数不允许创建临时变量，求字符串的长度。

• 非递归思路求法：

注意： 下面代码供参考，但不能用，因为函数用到了临时变量 count 来计数，而题目要求不允许创建临时变量

//求字符串"abc"的长度
//模拟实现strlen求长度是不包括

#include
#include 
//这两种写法都是可以的
//int my_strlen(char str[])//参数部分写成数组的形式接收
int my_strlen(char* str)//参数部分写成指针的形式接收
{
	int count = 0;//计数，临时变量
	while (*str != '')
	{
		count++;//是字符就加1
		str++;//找下一个字符
	}
	return count;//返回计数的值，也就是字符串"abc"的长度
}
int main()
{
	char arr[] = "abc";//[a b c ] ，数组传参传的是首字母地址
	//char* 
	int len = my_strlen(arr);//求字符串长度函数

	printf("%dn", len);

	return 0;
}

• 递归解法思路代码：

//递归求解
//思路：
//my_strlen("abc");
//1+my_strlen("bc");
//1+1+my_strlen("c")
//1+1+1+my_strlen("")
//1+1+1+0

int my_strlen(char* str)
{
	//str != '',说明长度至少是1
	//str指的是a的地址，str+1就会指向b的地址，向后看就是bc
	if (*str != '')
		return 1 + my_strlen(str+1);
	else
		return 0;//当等于o时，字符串长度等于0，所以返回0
}
int main()
{
	char arr[] = "abc";//[a b c ]
	//char* 
	int len = my_strlen(arr);

	printf("%dn", len);

	return 0;
}

（2）函数递归的过程（画图）

画图能很好帮助我们理解递归的过程，在图中我们可以看到递归是函数在调用自身的写法，然后一直递，递到限制条件，不能递，然后开始归。要把递归两字拆开去理解它，我图画的比较潦草家人们一定要仔细看先看蓝线递，后看红线归，看图时可以结合我上面代码注解，可以更好理解

递归与迭代 —— 练习3，练习4 ，延伸：栈溢出

迭代：循环等于迭代，但迭代不止于循环，迭代可以说是非递归

练习3

求n的阶乘。（不考虑溢出）

• 递归求法：

由n的阶乘的特性我们得到上面这个公式，那我们就可以写出如下递归代码：

//递归实现
#include
int fac(int n)
{
	if (n <= 1)
		return 1;
	else if (n > 1)
		return n * fac(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fac(n);
	printf("ret = %dn", ret);
	return 0;
}

• 迭代求法：

n的阶乘我在上一章说过，如果看不明白的可以去上一章循环看，看完后这个n的阶乘迭代实现就很容易理解了

//迭代的方式-非递归：循环等于迭代，迭代不止循环
#include
int fac(int n)
{
	int i = 0;
	int ret = 1;
	for (i = 1; i <= n; i++)
	{
		ret =ret * i;
	}

	return ret;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fac(n);
	printf("ret = %dn", ret);
	return 0;
}

• 注意虽然说我们递归很重要，但不是所有问题都用递归的形式去解决，当递归递的太深，也就是函数调用自身次数太多会出现死递归（栈溢出），此时采用非递归（迭代）的方式解决会更好。如练习4，求第n个斐波那契数。（不考虑溢出）

练习4

求第n个斐波那契数。（不考虑溢出）

• 递归实现：

由斐波那契数的特性可得上面这个公式，写出如下递归代码：

//求第n个斐波那契数
//斐波那契数列
//1 1 2 3 5 8 13 21 34 55 ...


int count = 0;//计数器验证递归求斐波那契数效率不高
//递归求法
int Fib(int n)
{
	if (n == 3)//计数器验证递归求斐波那契数效率不高
		count++;

	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("%dn", ret);

   //计数器验证递归求斐波那契数效率不高，如50就栈溢出，40则计算结果变慢
	printf("%dn", count);
	return 0;
}

在上面代码中我增加了一个全局变量count，用来统计我们所要求斐波那契数，包含第三个斐波那契数多少个，比如求第7个数那包含了5个第三个斐波那契数 ，且如果我们所求的斐波那契数越大，他包含第三个越多，计算量越大，会导致栈溢出,程序崩溃,如50就栈溢出，40则计算结果变慢
我们可以看一下求第四十个斐波那契数所包含第三个有多大，可以看到，3900多万，递归实现调用自身这么深计算量十分巨大，到50电脑基本算不出来了，很慢，不信的小伙伴可以去试一下

像递归解决求斐波那契数时，会重复大量计算，效率低，这时就得用到非递归的形式去求效率更好更高

• 非递归实现（迭代）

非递归思路图示：

代码实现：

//迭代—非递归求法
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 0;

	while (n >= 3)
	{
		c = a + b;
		a = b;//把b赋给a
		b = c;
	   //n--避免死循环，n==3时，也就是第三位时计算是1次，
	   //n==4时，也就是第三位时计算是2次
		n--;
	}

	return c;//返回结果值
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%dn", ret);

	return 0;
}

这时去计算50次一下结果就出来了，但计算结果会不准确因为超出int范围

• 递归太深，会栈溢出

阅读上面讲解我们大概明白了栈溢出，了解了递归，为了加深一下印象有一个代码就是递归调用自身次数太多，导致的栈溢出

//递归太深，会栈溢出

void test(int n)
{
	if (n < 10000)
		test(n + 1);//n~10000，太深，栈溢出
}

int main()
{
	test(1);
	return 0;
}

• 提示：
  1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
  2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
  3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开
  销

一些个人的垃圾话：

写到这里前三节课差不多总结完了，离我发布上一篇好像过去差不多两个月吧，有很多个人原因，这里就不多说了，我唯一能说的是当我们决定一件事的时候就去做，然后不要停下来，因为当你停下来时，你会发现再启动时难于登天！！！希望我们都能坚持不逃避，感谢你看到这里，晚安！！！

暑期编程PK赛 得CSDN机械键盘等精美礼品！