3.函数（递归+栈帧）

函数的定义

维基百科中将函数定义子程序

c语言中函数的分类

1. 库函数

2. 自定义函数

库函数

库函数的使用，一定要包含#include对应的头文件

对照文档学习， 自己去掌握库函数的使用方法

查找和学习的网址：cplusplus网站

//初期c语言
//1. 开发效率低
//2. 标准
//3. 容易出bug

//为了解决这些问题
//c语言的编译器提供了一些库函数
//vs - 微软
//gcc - gcc官方
//clang - 苹果官方

//c语言的标准做了一些工作
//对函数名，功能，参数，返回类型进行了规定

//然后厂商将函数进行实现
//printf
//scanf
//strlen
//...
//以上的函数被称为库函数，可以直接拿来使用

c语言中常用的库函数：

• io函数
• 字符串函数
• 字符串操作函数
• 内存操作函数
• 时间/日期函数
• 数学函数
• 其他库函数

最近学习：

• 当我们进行字符串的输入时，可以使用gets()函数，传入char *（数组首地址）即可，返回值也为char *。该函数适用于当字符串中有空格（I love you）时。

• 我们看到scanf()函数，输入的是“i love you”，而输出的只有“i”。原因是系统将空格作为输入字符串之间的分隔符。也就是说，只要一“敲”空格，系统就认为当前的字符串已经结束，接下来输入的是下一个字符串，所以只会将空格之前的字符串存储到定义好的字符数组中。

# include <stdio.h>
int main(void)
{
    char str[10];  //str是string的缩写, 即字符串
    printf("请输入字符串：");
    scanf("%s", str);  //输入参数是已经定义好的字符数组名
    printf("输出结果：%s\n", str);
    return 0;
}

• 因此我们可以将代码改为：

# include <stdio.h>
int main(void)
{
    char str[10];  //str是string的缩写, 即字符串
    printf("请输入字符串：");
   	gets(str);
    printf("输出结果：%s\n", str);
    return 0;
}

自定义函数

库函数并不能解决所有问题，因此自定义函数非常重要

自定义函数也有函数名、返回值类型和函数参数

但这些都需要我们自己来设计，程序员有着很大的发挥空间

语法结构

ret_type fun_name(para1,* ){
  statement;//语句项
}
//ret_type 返回类型
//fun_name 函数名
//para1    函数参数

举例说明

• 用函数实现两个数的交换

#include <stdio.h>
//实现成函数，但是不能完成任务
void Swap1(int x, int y) {
	int tmp = 0;
	tmp = x;
	x = y;
	y = tmp; 
}
//正确的版本
void Swap2(int *px, int *py) {
	int tmp = 0;
	tmp = *px;
	*px = *py;
	*py = tmp; 
}

int main()
{
	int num1 = 1;
	int num2 = 2;
	Swap1(num1, num2);
	printf("Swap1::num1 = %d num2 = %d\n", num1, num2);
	Swap2(&num1, &num2);
	printf("Swap2::num1 = %d num2 = %d\n", num1, num2);
	return 0; 
}

函数的参数

实际参数（实参）

真实传给函数的参数，叫实参。

实参可以是：常量、变量、表达式、函数等。

无论实参是何种类型的量，在进行函数调用时，它们都必须有确定的值，以便把这些值传送给形参。

形式参数（形参）

形式参数是指函数名后括号中的变量，因为形式参数只有在函数被调用的过程中才实例化（分配内存单元），所以叫形式参数。

形式参数当函数调用完成之后就自动销毁了。因此形式参数只在函数中有效。

举例说明：

• 上面 Swap1 和 Swap2 函数中的参数 x，y，px，py 都是形式参数。
• 在main函数中传给 Swap1 的 num1 ，num2 和传给 Swap2 函数的 &num1 ， &num2 是实际参数。
• 这里可以看到 Swap1 函数在调用的时候， x ， y 拥有自己的空间，同时拥有了和实参一模一样的内容。

所以我们可以简单的认为：形参实例化之后其实相当于实参的一份临时拷贝。

函数的调用

传值调用

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

传址调用

传址调用是把函数外部创建变量的内存地址传递给函数参数的一种调用函数的方式。

这种传参方式可以让函数和函数外边的变量建立起真正的联系，也就是函数内部可以直接操作函数外部的变量。

函数的嵌套调用和链式访问

函数和函数之间可以根据实际的需求进行组合的，也就是互相调用的。

嵌套调用

#include <stdio.h>
void new_line()
{
 	printf("hehe\n");
}
void three_line()
{
    int i = 0;
 	for(i=0; i<3; i++)
    {
        new_line();
    }
}
int main()
{
 	three_line();
 	return 0; 
}

• 函数可以嵌套调用，但是不能嵌套定义。

链式访问

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

举例1：

#include <stdio.h>
#include <string.h>
int main()
{
    char arr[20] = "hello";
 	int ret = strlen(strcat(arr,"world "));
 	printf("%d\n", ret);
 	return 0; 
}

• strcat的用法：destination为原字符串，source为新追加于后面的字符串，返回添加后的字符串。（destination中的’\0’字符被的source第一个字符覆盖。两者的串联形成的新字符串，结尾含有’\0’）

char * strcat ( char * destination, const char * source );

• strlen的用法：返回获取字符串长度，str字符串的长度由终止空字符确定，str字符串的长度与字符串开头和终止空字符之间的字符数一样长（不包括终止空字符本身）。

size_t strlen ( const char * str );

• 因此ret的结果为hello world字符串的长度为：11

举例2：

#include <stdio.h>
int main()
{
    printf("%d", printf("%d", printf("%d", 43)));
    //结果是啥？
    //注：printf函数的返回值是打印在屏幕上字符的个数
    return 0; 
}

• 同理结果为：4321

函数的声明和定义

函数声明

告诉编译器有一个函数叫什么，参数是什么，返回类型是什么。但是具体是不是存在，函数声明决定不了。

函数的声明一般出现在函数的使用之前。要满足先声明后使用。

函数声明一般要放在头文件中。

test.h的内容

放置函数的声明

#ifndef __TEST_H__
#define __TEST_H__
//函数的声明
int Add(int x, int y);

#endif //__TEST_H__

函数定义

函数的定义是指函数的具体实现，交待函数的功能实现。

test.c的内容

放置函数的实现

#include "test.h"
//函数Add的实现
int Add(int x, int y) {
 	return x+y; 
}

• 这种书写形式做大型项目时会更加合适

函数递归

递归的定义

程序调用自身的编程技巧称为递归（ recursion）。

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。

它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的两个必要条件

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

递归的过程

求n的阶乘代码：

int fact(int n)
{
    if(n==0) return 1;
    else return fact(n-1)*n;
}

调用过程：

• 层层调用：只有当算出了程序递归最深处的值，也就是递归的出口才会一层层计算后返回。

递归和迭代

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

递归代码：

int fib(int n) {
 if (n <= 2)         
 	return 1;
 else
    return fib(n - 1) + fib(n - 2);
}

但是我们发现有问题：

• 在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。
• 使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。

原因：

• 我们发现 fib 函数在调用的过程中很多计算其实在一直重复。如果我们把代码如下：

int count = 0;//全局变量
int fib(int n){
 if(n == 3)
 	count++;
 if (n <= 2)         
	return 1;
 else
    return fib(n - 1) + fib(n - 2);
}

• 最后我们输出看看count，是一个很大很大的值（当计算第20个斐波那契数时，第三项计算了2584次）。

• 在调试 factorial 函数的时候，如果你的参数比较大，那就会报错： **stack overflow（栈溢出）**这样的信息。
• 系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者死递归，这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

改进：

1. 将递归改写成非递归（迭代）。

int fib(int n) {
     int result;
     int pre_result;
     result = pre_result = 1;
  	 while (n >= 2)
     {
           int t = pre_result;
           pre_result = result;
           result = pre_result + t;
       	   n--;
     }
     return result; 
}

//求第n个斐波那契数
int fib(int n) {
     int result;
     int pre_result;
     int next_older_result;
     result = pre_result = 1;
  	 while (n > 2)
     {
           n -= 1;
           next_older_result = pre_result;
           pre_result = result;
           result = pre_result + next_older_result;
     }
     return result; 
}

2. 使用static对象替代 nonstatic 局部对象（即栈对象）。
   • 这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销。
   • 而且 static 对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。

提示：

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

递归经典题目

汉诺塔问题

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

• 首先我们可以看出，因为一次只能移动一个圆盘，小圆盘上不能放大圆盘，所以我们可以先假设a柱子上只剩一个圆盘时应该直接a - > c。
• 因此我们可以先将上面n-1个圆盘放到b上。想要放到b上，则需要将c作为中间站，进行一次递归。
• 然后即可把最后一个在a上的圆盘移动到c上。

• 此时，我们的题目就变成了把a作为中间站，将b中剩下的n-1个圆盘移动到c上。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void move(int x, int y)
{
	printf("%c->%c\n", x, y);
}
void hanoi(int n, char a, char b, char c)
{
	if (n == 1)
	{
		move(a, c);
	}
	else
	{
		hanoi(n - 1, a, c, b);//将A座上的n-1个盘子借助C座移向B座
		move(a, c);//将A座上最后一个盘子移向C座
		hanoi(n - 1, b, a, c);//将B座上的n-1个盘子借助A座移向C座
	} 
}
//move中的实参与hanoi函数中的形参相对应，而hanoi函数中形参a，b，c所对应的值也是在有规律的变化
int main()
{
	int n = 0;
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}

青蛙跳台阶问题

一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。

分析：

• 当n = 1时，有1种跳法；
• 当n = 2时，有2种跳法；
• 当n = 3时，有3种跳法；
• 当n = 4时，有5种跳法；
• 当n = 5时，有8种跳法；
• …类似于斐波那契数列

int Fib(int n)
{
	if (n <= 0)
	{
		cout << "error!" << endl;
		return -1;
	}
 
	if (1 == n)
	{
		return 1;
	}
	else if (2 == n)
	{
		return 2;
	}
	else
	{
		return Fib(n - 1) + Fib(n - 2);
	}
}

函数栈帧

寄存器

寄存器的功能是存储二进制代码，它是由具有存储功能的触发器组合起来构成的。

寄存器	用途用途
EAX	累加寄存器：用于乘除法、函数返回值
EBX	用于存放内存数据指针
ECX	计数器
EDX	用于乘除法、IO指针
ESI	源索引寄存器，存放源字符串指针
EDI	目标索引寄存器，存放目标字符串指针
ESP	存放栈顶指针
EBP	存放栈底指针

寄存器有很多种类：我们这里使用的ebp和esp寄存器存放的地址是用来维护函数栈帧的。

汇编指令

汇编指令是汇编语言中使用的一些操作符和助记符，还包括一些伪指令（如assume，end），汇编指令同机器指令一一对应。每一种CPU都有自己的汇编指令集。

汇编指令	用途
mov	mov A,B 将数据B移动到A
push	压栈
pop	出栈
call	函数调用
add	加法
sub	减法
rep	重复
lea	加载有效地址
cmp	减法（不保存）

栈帧的定义

C语言中，每个栈帧对应着一个未运行完的函数。栈帧中保存了该函数的返回地址和局部变量。

分析：

• 栈帧是一块因函数运行而临时开辟的空间。
• 每调用一次函数便会创建一个独立栈帧。
• 栈帧中存放的是函数中的必要信息，如局部变量、函数传参、返回值等。
• 当函数运行完毕栈帧将会销毁。

举例代码：

int Add(int a, int b){
  	int c = 0;
  	c = a + b;
  	return c;
}

int main(){
  	int a = 10;
  	int b = 20;
  	int ret = 0;
  	ret = Add(a, b);
  	printf("%d\n", ret);
  	return 0;
}

main函数栈帧创建

根据VS2013编译器调试，调用堆栈，不难发现main函数的调用链条如下：

• 很显然main函数在被调用时，创建了栈帧。在调试过程中将转到反汇编，便能直观的看到main函数栈帧创建的过程。首先需明确的是，函数栈帧由寄存器esp,ebp维护。

• 分析汇编代码可知：
  • 首先在__tmainCRTStartup()函数顶部压入ebp，如图所示esp指向ebp，ebp成功压入栈中。
  • esp值传递给ebp。
  • esp减去0E4h：由于栈先使用高地址后使用低地址，减去一个值意味着esp指针向低地址移动了0E4h个地址，此处便开辟了main函数的栈帧。
  • 压入ebx，esp指向ebx顶部。
  • 压入esi，esp指向esi顶部。
  • 压入edi，esp指向edi顶部。
  • 将edi向下24h个空间全部改为0xCCCCCCCC。

动态演示：

局部变量的创建

同样我们观察汇编代码可知：

• 将十六进制整数：0Ah（DEC 10）放入ebp 向低地址移动8个字节。
• 将十六进制整数：14h（DEC 20）放入ebp 向低地址移动20个字节。
• 将十六进制整数：0（DEC 0）放入ebp 向低地址移动32个字节。

动态演示 ：

函数传参与调用

从以上汇编代码可知函数是先传参后调用，函数传参顺序是从右往左。

函数传参

• ebp - 14h 的地址传给eax，即eax中实际存放了20。
• eax 压栈。
• ebp - 8 的地址传给ecx，即ecx中实际存放了10。
• ecx 压栈。

动态演示 ：

函数调用

可以发现，在执行call指令后，栈中压入call指令的下一条地址。

进入Add()函数，可以看出这与此前main函数开辟栈帧的过程类似，说明Add()函数调用又开辟了一块独立的栈帧。

在函数栈帧、局部变量创建完毕后，进行Add()函数运算过程：

• 将（ebp + 8）的值传递给eax，此时的ebp存放Add函数的栈底指针，（ebp + 8） 的位置即函数传参时创建的ecx的地址，其内部存放的正是10。
• eax寄存器中执行求和指令，加上（ebp + 0ch) 中的值，同理可以得知（ebp + 0ch）中的值是20。
• 将eax的经过求和的结果，传递到（ebp - 8）的位置 。

通过上述过程可以得知函数内部并未给形参开辟空间，而是直接查找了实参传递时的地址，由此解释了形参其实是实参的一份临时拷贝。

动态演示 ：

函数返回

将返回值传递至寄存器eax中，因此在函数调用结束函数栈帧被销毁时，返回值并不会销毁。在函数拿到返回值后，开始出栈：

• 从低位置到高位置依次弹出edi，esi，ebx。
• 执行指令 add esp,0CCh，将esp的位置恢复到当前ebp的位置，当前ebp就是main函数的栈帧顶部。
• ebp 出栈，将出栈的内容给ebp（即main()函数ebp），回到main()函数的栈帧。
• ret 指令，出栈一次，并将出栈的内容当做地址，并跳转到该地址处（pop+jmp）。

主函数的返回同理。

函数堆栈框架

call xxx

• 执行call之前;
• 执行call时，cs:eip原来的值指向call下一条指令，该值被保存到栈顶，然后cs:eip的值指向xxx的入口地址。
• 进入xxx
• 第一条指令：pushl %ebp
• 第二条指令：movl %esp,%ebp
• 函数体中的常规操作，压栈，出栈等

退出xxx

• movl %ebp,%esp
• popl %ebp
• ret