函数（2）

6. 函数的声明和定义

6.1 函数声明：

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

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

int main()
{
	int num1 = 0;
	int num2 = 0;
	scanf("%d %d", &num1, &num2);
	//计算
	//函数的调用（传值调用）
	//2
	int ret = Add(num1, num2);
	printf("%dn", ret);

	return 0;
}

//函数的定义
int Add(int x, int y)
{
	return x + y;
}

6.2 函数定义

函数的定义是指函数的具体实现，交待函数的功能实现。
函数的定义本就是一种特殊的声明。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//函数的定义
int Add(int x, int y)
{
	return x + y;
}

int main()
{
	int num1 = 0;
	int num2 = 0;
	scanf("%d %d", &num1, &num2);
	//计算
	//函数的调用（传值调用）
	//2
	int ret = Add(num1, num2);
	printf("%dn", ret);

	return 0;
}

以后我们可以把函数的声明放在同一头文件中，这样方便管理。

7. 函数递归

7.1 什么是递归？

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

7.2 递归的两个必要条件

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

7.2.1 练习1：

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

不用递归的方法得到的是这样的

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
	int num = 0;
	scanf("%d", &num);
	while (num)
	{
		printf("%d ", num%10);
		num = num / 10;
	}
	return 0;
}

我们用递归来实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Print(int n)
{
	if (n > 9)
	{
		Print(n/10);
	}
	printf("%d ", n % 10);
}
int main()
{
	int num = 0;
	scanf("%d", &num);//1234

	Print(num);

	return 0;
}

其实递归分为两步，递推和回归，我们把递推实现到最后一步再进行回归。

7.2.2 练习2：

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

大家都知道求字符串长度用strlen就可以了，但是我们用递归的方式也能够实现。

实现我们来看一下strlen实现,strlen函数是统计/0之前的字符串长度，遇到/0就会停止。

strlen这个函数的返回类型是size_t，size_t 类型的数据打印的时候使用%zd，size_t 是一种类型，是无符号整型的，size_t就是为sizeof设计的。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
int main()
{
	char arr[] = "abc";
	size_t len = strlen(arr);
	printf("%zdn", len);

	return 0;
}

我们用递归来实现一下：

用递归来实现的话就相当于模拟实现strlen。数组传参的话传过去的是首元素的地址，传过去的是a的地址，所以我们用char*来接收，我们用if来判断首元素是不是/0，如果不是则+1并且（str+1）统计下一位元素，如此循环往复就可以进行递归了，直到遇到/0停下来。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
size_t my_strlen(char* str)
{
	if (*str == '')
		return 0;
	else
		return 1 + my_strlen(str + 1);
}
int main()
{
	char arr[] = "abc";
	size_t len = my_strlen(arr);//传递的是数组首元素的地址
	printf("%zdn", len);

	return 0;
}

7.3 递归与迭代

7.3.1 练习3：

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

在数学里面阶乘就是这样定义的，我们可以发现用递归来实现就很容易了。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int Fac(int n)
{
	if (n <= 1)
		return 1;
	else
		return n* Fac(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int r = Fac(n);
	printf("%dn", r);

	return 0;
}

7.3.2 练习4：

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

斐波那契·数就是前面二个数等于第三个数。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
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("%dn", ret);

	return 0;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n >= 3)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%dn", ret);

	return 0;
}

但是我们发现有问题；
在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。
使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。
为什么呢？
我们发现 fib 函数在调用的过程中很多计算其实在一直重复。
提示：
1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

这篇文章到这里就结束啦！感谢烙铁们的阅读，下篇我们将详细的讲解数组，让我们下期再见。