目录
6. 函数的声明和定义
7.函数递归
7.1 什么是递归？
7.2 递归的两个必要条件
7.2.1 练习1：（递归做法在方法二）
7.2.2 练习2：（递归做法在最后）
编写函数不允许创建临时变量，求字符串的长度。
7.3 递归与迭代
7.3.1 练习3：
求n的阶乘。（不考虑溢出）
7.3.2 练习4：
求第n个斐波那契数。（不考虑溢出）
6. 函数的声明和定义
通过以下例子来体会函数声明和定义。
定义一个加法函数
1、在主函数之前定义
#includeint Add(int x, int y) { return x + y; } int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b);//30 40 //加法 int sum = Add(a, b); printf("%dn", sum); return 0; }
2、在主函数之后定义
#includeint main() { int a = 0; int b = 0; scanf("%d %d", &a, &b);//30 40 //加法 int sum = Add(a, b); printf("%dn", sum); return 0; } //函数的定义 int Add(int x, int y) { return x + y; }
这时候，为了防止编译器报警告，说Add未定义，要进行函数的声明
函数的声明：告诉编译器我有一个函数，具体是不是存在，函数声明决定不了
函数的声明，只要有返回类型，函数名，参数类型就够了
函数声明一般出现在函数使用之前，要先声明后使用
函数的定义：真真实实创建一个函数，函数真正有没有存在取决于函数的定义
如下：
#include//函数的声明 int Add(int x, int y); int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b);//30 40 //加法 int sum = Add(a, b); printf("%dn", sum); return 0; } //函数的定义 int Add(int x, int y) { return x + y; }
但其实在实际操作中，我们一般会将加法看成一个模块，将函数的声明放在头文件中。
函数的声明一般要放在头文件（.h）中
将加法函数的声明放在add.h,加法函数的定义放在add.c中
具体写法如下：
肯定有同学会有疑问，那我放在两个.c文件中不就可以了吗，为什么还要有一个.h头文件呢
没有add.h文件，只有add.c与test.c文件的加法函数写法如下（可以用extern来声明外部函数）
（关于函数的声明需要用extern吗？函数头文件的声明前需不需要加extern？这个问题目前还未彻底理解，暂时认为加不加应该都可以。）
那么为什么我们要造出来一个.h文件，而且在常规设计中也有这个.h文件呢？
把一个函数的加法模块拆成一个函数的声明(一个头文件)和一个函数的定义(一个源文件)
好处：
1、将函数声明放在.h文件中，然后包含了这个.h文件，就相当于将函数声明拷贝了过来，实现了函数声明的效果
2、将函数的实现(.c)和函数的声明(.h)分开，可以将.c文件变成.lib静态库，然后可以将.h和.lib打包给别人，别人就可以用了，同时可以防止源代码泄露。
所以，要拆分好多模块来写
所以，函数的声明一般要放在头文件中，定义放在另一个源文件中，包含头文件就可以使用对应的代码，这才是真正的函数应该有的样子
3、使思路更清晰等等好处
7.函数递归
7.1 什么是递归？
程序调用自身的编程技巧称为递归。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的 一种方法，
它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
递归策略：
只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小
7.2 递归的两个必要条件
1、存在限制条件，当满足这个限制条件的时候，递归便不再继续。
2、每次递归调用之后越来越接近这个限制条件。
没有这两个条件一定错！！会导致栈溢出。有这两个条件也有可能会错。这就是必要条件。
程序调用自身的编程技巧称为递归。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的 一种方法，
它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
递归策略：
只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小
7.2 递归的两个必要条件
1、存在限制条件，当满足这个限制条件的时候，递归便不再继续。
2、每次递归调用之后越来越接近这个限制条件。
没有这两个条件一定错！！会导致栈溢出。有这两个条件也有可能会错。这就是必要条件。
1、存在限制条件，当满足这个限制条件的时候，递归便不再继续。
2、每次递归调用之后越来越接近这个限制条件。
没有这两个条件一定错！！会导致栈溢出。有这两个条件也有可能会错。这就是必要条件。
下面通过几道练习来深入了解何为递归
7.2.1 练习1：（递归做法在方法二）
接受一个整型值（无符号），按照顺序打印它的每一位。 例如： 输入：1234，输出 1 2 3 4.
%d - 打印有符号的整数（会有正负数）
%u - 打印无符号的整数（没有负数）
下面是两种错误的做法，但可能会对其他题提供一些思路，所以我也记录了下来。
这种方法适合于你已经知道输入的整数是多少位时：（%md / %mu:只读入m位整数）
假设输入的是4位整数 ，代码如下
#includeint main() { unsigned int a = 0, b = 0, c = 0, d = 0; scanf("%1u%1u%1u%1u",&a,&b,&c,&d); printf("%u %u %u %u",a,b,c,d); return 0; }
这种方法是倒序打印每一位，不符合题意，但在此基础上修改一下，用数组存起来倒着打印就符合题意了，就得到了下面的方法一
倒序打印每一位，代码如下
#includeint main() { unsigned int num = 0; scanf("%u",&num);//1234 while (num) { printf("%u ",num%10);//4 3 2 1 num = num / 10; } return 0; }
下面是正确的做法
方法一：
用取模方式依次取出最后一位，然后用数组存起来后倒着打印
#includeint main() { unsigned int num = 0; unsigned int arr[10] = { 0 }; int i = 0; scanf("%u", &num);//这里用%u while (num) { arr[i] = num % 10; i++; num = num / 10; } int j = 0; for (j = i - 1; j >= 0; j--) { printf("%u ", arr[j]); } return 0; }
方法二：（递归实现）推荐
解题思路： print(1234)
print(123) 4
print(12) 3 4
print(1) 2 3 4
1 2 3 4
代码如下：
#includevoid print(unsigned int num) { if (num > 9) { print(num / 10); } printf("%u ", num % 10); } int main() { unsigned int num = 0; scanf("%u",&num); print(num);//print()这个函数的作用就是按照顺序打印每一位 return 0; }
通过下图可以进一步理解
递归实现：先递后归
可能有同学会有疑问，为什么归时，num还是传入的那个12，而不是n/10后的1
因为n/10只是将n除10传过去，但是并没有改变n的值
比如下面这个例子
#includeint main() { int a = 30; int z = a % 10;//0 int t = a / 10;//3 printf("%d %d %d", a, z, t);//30 0 30 return 0; }
我将a%10，或将a/10,但是a本身是没变的，只有我定义一个变量z=a%10，这个z才和a不同
想要a改变， a = a%10,这样a才能改变。
如果看到这里对递归的理解还是有些模糊，不要着急，慢慢来。
我是这样理解的。
我们先来看一下函数的嵌套（函数的嵌套调用在上篇博客中提到过），函数的嵌套调用就是一个函数中调用另一个函数。
函数的递归是自己调用自己，和函数的嵌套不严谨的说是类似的。
下面用函数嵌套调用来举个例子，输入一个两位的整数，按顺序依次输出，代码如下
#include//函数嵌套调用， void new_print(int num)//1 //形参：当函数调用完后形式参数就自动销毁了 { printf("%d ", num % 10);//1 } void print(int num)//12 //形参 { if (num > 9) { new_print(num/10);// //实参 } printf("%d ", num % 10);//2 } int main() { int num = 0; scanf("%d",&num);//12 print(num); //实参 return 0; }
图解如下：
是不是感觉和函数的递归很像呢。希望能给看到这的你提供一些思路嘿嘿。
7.2.2 练习2：（递归做法在最后）
编写函数不允许创建临时变量，求字符串的长度。
首先，如何求字符串长度呢？
代码如下
#include#include int main() { int len = strlen("abc"); printf("%dn",len);//3 return 0; }
那如何编写函数求字符串长度呢，这就需要我们模拟实现strlen
代码如下
#includeint my_strlen(char* str) // { int count = 0;//计数 while (*str != ' ') { count++; str++; //找下一个字符 } return count; } int main() { int len = my_strlen("abc");// printf("%dn",len);//3 return 0; }
说明：
1、参数部分写成 int my_strlen(char str[ ]) 或 int my_strlen(char* str) 都可以，前者是数组的形式，后者是指针的形式。
2、
int len = my_strlen("abc");字符串传给my_strlen传的不是字符串本身，传的是首元素a的地址，（要用指针来接收）
字符串在内存中也是一个连续的存放，当知道首字符的地址时，就可以找到所有字符了
字符串传参时和数组很类似，上面那个代码就相当于char arr[] = "abc"; // [a b c ] int len = my_strlen(arr);
图解：
但是上面这种做法创建了临时变量count用来计数，
题目要求编写函数不允许创建临时变量，求字符串的长度。
于是有了下面这种做法（递归的做法）！！
解题思路：
my_strlen("abc")
1 + my_strlen("bc")
1 + 1 + my_strlen("c")
1 + 1 + 1 + my_strlen("")
1 + 1 + 1 + 0
#includeint my_strlen(char* str) { if (*str != ' ') { return 1 + my_strlen(str + 1); } else { return 0; } } int main() { char arr[] = "abc"; int len = my_strlen(arr);// [a b c ] printf("%dn",len); return 0; }
看到这里的你可能会发现模模糊糊能理解递归，但是自己写的话还是不会
慢慢来，刚开始听懂不会写很正常，不要着急 ，这需要一个过程。
7.3 递归与迭代
迭代就是重复
循环是一种迭代，迭代不仅仅是循环
7.3.1 练习3：
求n的阶乘。（不考虑溢出）
迭代就是重复
循环是一种迭代，迭代不仅仅是循环
求n的阶乘。（不考虑溢出）
方法一：递归实现
#includeint fac(int num) { if (num <= 1) { return 1; } else { return num * fac(num - 1); } } int main() { int num = 0; scanf("%d",&num); int ret = fac(num); printf("%dn",ret); return 0; }
方法二：迭代的方式——非递归
#includeint fac(int num) { int i = 0; int ret = 1; for (i = 1; i <= num; i++) { ret = ret * i; } return ret; } int main() { int num = 0; scanf("%d",&num); int ret = fac(num); printf("%dn",ret); return 0; }
运行结果：
7.3.2 练习4：
求第n个斐波那契数。（不考虑溢出）
斐波那契数列：
1 1 2 3 5 8 13 21 34 55 前两个数相加等于第三个数
斐波那契数列：
1 1 2 3 5 8 13 21 34 55 前两个数相加等于第三个数
方法一：递归（不推荐，有太多重复运算）
公式： Fib(n) = 1 ,n <= 2
=Fib(n-1) + Fib(n-2) ,n > 2
#includeint 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); printf("%dn",count); return 0; }
递归的计算过程：
40
39 38
38 37 37 36
37 36 36 35 36 35 35 34
...
计算第40个斐波那契数时，3这个数就被重复计算了39088169次，有太多重复运算
所以我们用迭代来求斐波那契数比较好。
方法二：迭代
解题思路：
代码：
#includeint 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; }
有时候用递归去解决问题会出现效率低，那如何权衡，是用递归还是不用递归呢？
写代码过程中，如果用递归写代码很简单并且没有什么缺陷，就用递归
如果有缺陷，出现效率低下或栈溢出，就用非递归方法。
