# 课堂笔记

# 递归函数

递归函数是直接或间接地调用了自身的函数。
利用递归算法可以将一个规模较大的问题转化为规模较小的同类问题来求解。

# 例子：计算一个非负整数 n!

$$f{(n)} = \begin{cases} 1 & n=0 \\ n*f{(n-1)} & n>0 \end{cases}$$

• 特征：

  1. 定义中包含该函数本身（即递归公式）
  2. 必须有终止条件

• 调用过程包括：

  1. 递推：将原问题不断分解为新的规模更小的问题，逐渐从未知向已知方向推测。
  2. 回归：是从已知条件出发，按递推的逆过程，逐个求值，最后到达递推的开头，解决原问题。

int f(int n) // 计算 n!

{

	if(n==0) 

	{

		return 1;

	}

	else 

	{

		return n*f(n-1); // 直接递归调用

	}

}

# 例子：Hanoi 汉诺塔问题

有 A,B,C 三根柱子，在 A 柱子上有 n 个大小不同的金盘，大盘在下，小盘在上。
要将 A 柱子上的金盘移动到 C 柱子上，每次只能搬动一个金盘，搬动过程中可以借助任何一根柱子暂时存放金盘，但必须满足大盘在下，小盘在上的条件。
编程显示盘子移动的过程。n 由用户输入。

# 算法分析

• 如果只有一个盘子，只需一步，直接从 A 柱移动到 C 柱，用 A ➡️ C 表示；

• 如果有 2 个盘子，共需要移动 3 步:

  1. 把 A 柱上的小盘子移动到 B 柱；用 A ➡️ B 表示；
  2. 把 A 柱上的大盘子移动到 C 柱；用 A ➡️ C 表示；
  3. 把 B 柱上的小盘子移动到 C 柱；用 B ➡️ C 表示；

• 如果要将 A 柱上的 n 个盘子（n 值较大），移动到 C 柱上去，必须先把
  上面的 n-1 个盘子从 A 柱移动到 B 柱上暂存，按这种思路，就可以把 n 个盘子的移动过程分作三大步：

  1. 把 A 柱上面的 n-1 个盘子移动到 B 柱；
  2. 把 A 柱上剩下的一个盘子移动到 C 柱；
  3. 把 B 柱上面的 n-1 个盘子移动到 C 柱；

• 其中 n-1 个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。

# 算法描述

hanoi (n,A,B,C)
	如果 n=1, 则
		显示 A--->C // 将一个金盘直接从 A 移到 C 上
	否则
		hanoi (n-1,A,C,B) // 将 n-1 个金盘借助 C 从 A 移到 B 上
		显示 A--->C
		hanoi (n-1,B,A,C) // 将 n-1 个金盘借助 A 从 B 移到 C 上

# 代码实现

#include <iostream>

using namespace std;

int s=0; // 全局变量定义，用来记录总的移动次数

// 函数 move 将一个盘子从 x 移到 y

void move(char x,char y)

{

	cout<<x<<"---->"<<y<<endl;

	s++; //s 统计移动的次数

}

//hanoi 函数

void hanoi(int n, char a, char b, char c)

{

	if(n==1) {

		move(a,c);

	}

	else

	{

		hanoi(n-1,a,c,b); // 借助 c 将 n-1 个盘子从 a 移到 b

		move(a,c); // 从 a 移到 c

		hanoi(n-1,b,a,c); // 借助 a 将 n-1 个盘子从 b 移到 c

	}

}

int main()

{

	int m;

	cout<<"请输入盘子数：";

	cin>>m;

	cout<<"移动"<<m<<"个盘子的过程如下："<<endl;

	hanoi(m, 'A', 'B', 'C');

	cout<<"一共移动"<<s<<"次。"<<endl;

	return 0;

}

# 内联函数

程序通过一组函数实现是一种好的设计方法。但是函数调用涉及执行时间的开销。

C++ 提供的内联函数可以减少函数调用的开销。

inline <函数值类型> <函数名>(<形式参数表>)

{

	函数体

}

对用户来说，内联函数的定义与调用与普通函数的使用方法是相似的。

作为编译系统，它将程序中调用内联函数的语句（或表达式）用内联函数体中的代码进行替换。这样在执行时就避免了对内联函数的调用，从而减少了因函数调用所增加的时间开销，提高了程序运行的效率。

使用内联函数可以节省运行时间，但却增加了目标程序的长度。因此一般只将规模很小而使用频繁的简单函数声明为内联函数。

# 例子：内联函数的使用

编写程序，计算$1^2+ 2^2+ 3^2+…+ 10^2$，将计算整数平方的功能定义为内联函数。

inline int square(int x)

{

	return x*x;

}

int main()

{

	int i,sum=0;

	for(i=1;i<=10;i++) {

		sum+=square(i);

	}

	cout<<"sum="<<sum<<endl;

}

编译程序在遇到内联函数调用式 square(i) 时，就用 square 函数体中代码代替 square(i) ，同时将实参代替形参。这样语句 sum+=square(i); 将被替换为 sum+=i*i;

# 函数重载

函数重载是指在一个程序中，可以定义多个具有相同函数名，不同参数列表的函数（至少参数的类型或参数个数或参数类型的顺序不同）。这些的函数被称为重载函数。

当调用一个重载函数时，编译系统将通过检查函数调用中的实参个数、类型和顺序来选择恰当的函数。

重载函数通常用于实现功能类似，而所处理的数据类型不同的问题。

# 例子：形参个数相同，但类型不同

使用函数重载编写求一个整数和一个双精度数的绝对值的函数。

int Abs(int x)

{

	return x>=0?x:-x;

}

double Abs(double x)

{

	return x>=0?x:-x;

}

int main()

{

	int a=-3;

	double b=35.5;

	cout<<Abs(a)<<endl; // 3

	cout<<Abs(b)<<endl; // 35.5

	return 0;

}

# 例子：形参类型相同，但个数不同

使用函数重载编写求两个、三个以及四个整数的和的函数

int add(int x,int y)

{

	int sum;

	sum=x+y;

	return sum;

}

int add(int x,int y,int z)

{

	int sum;

	sum=x+y+z ;

	return sum;

}

int add(int x,int y,int z,int t)

{

	int sum;

	sum=x+y+z+t;

	return sum;

}

int main()

{

	cout<<add(3,5)<<endl;// 8

	cout<<add(3,5,7)<<endl;// 15

	cout<<add(3,5,7,9)<<endl;// 24

	return 0;

}

# 变量的作用域

变量的作用域是指变量的使用范围。
根据变量的使用范围不同，C++ 中的变量被分为局部变量和全局变量。

# 局部变量

在一个函数内或复合语句内定义的变量称为局部变量（函数的形参也属于局部变量）。

局部变量只允许在其定义的函数或复合语句中使用，离开所在的函数或复合语句后该局部变量将不能使用。

• 主函数中定义的变量，也不能在其它函数中使用。

int f(int n)

{

	for(int i=1;i<=n;i++) {

		sum+=i; // 错误，在函数 f 中，不能使用主函数中的 sum 变量，它属于主函数的局部变量。

	}

	return sum;

}

int main()

{

	int sum=0;

	sum=f(10);

	cout<<sum<<endl;

	return 0;

}

• 复合语句中定义的变量，也只能在该复合语句中使用。

int main()

{

	int i=1,j=3;

	cout<<i<<" " ;

	i++;

	{

		int i=0;

		i+=j*2;

		cout<<i<<", "<<j<<", ";

	}

	cout<<i<<", "<<j<<endl;

	// 结果 1,6,3,2,3

}

• for 语句中控制变量的作用域

int main()

{

	int a[]={34,56,23,41,33};

	int x;

	cin>>x;

	for(int i=0;i<5;i++)

	{

		if(x==a[i])break;

	}

	if(i<5) // 错误

	{

		cout<<"已找到，下标为："<<i<<endl;

	}

	else 

	{

		cout<<"未找到! "<<endl;

	}

	return 0;

}

编译系统（如：DEVC++），通常将循环语句中定义的变量作为局部变量处理，因此该变量在循环外是不能使用的。

局部变量是在执行该函数或复合语句时自动建立，当该函数或复合语句执行完毕后将自动释放。所以在不同的函数或复合语句中定义同名的局部变量，也不会相互干扰。局部变量也称为自动类型变量。

# 全局变量

全局变量说明于所有函数之外，可以为所有函数共同使用。
全局变量可以在各个函数之间建立数据的传输通道。

# 作用域运算符 ::

int a=3,b=5;// 定义两个全局变量

int max(int a,int b)

{

	return a>b?a:b;

}

int main()

{

	int a=8;

	cout<<max(::a,b)<<endl; // 结果为 5

}

注意：
在函数中，当局部变量与全局变量同名时，遵循 “局部变量优先” 的原则。
这时，如果想使用全局变量，应在变量名前加上作用域运算符 :: 即可。

# extern 声明

全局变量的作用范围是从定义点到整个源程序的结束。在定义点之前，如果
其它函数要引用全局变量，可以在该函数中用 extern 对全局变量进行声明。

F1()

{

	extern a,b; // 全局变量声明

	<使用全局变量a,b>

}

F2()

{

}

int a=2,b=5; // 全局变量定义

# 优缺点

• 使用全局变量，可以增加函数间的直接联系，减少函数定义时的参数。

• 由于全局变量在整个程序运行中始终占用内存，这样，使用全局变量将降低程序的通用性、可靠性和移植性，这是全局变量的负面作用。

# 变量的存储类型

不同的变量所分配的存储区域也不同，这就是变量的存储类型。

# 内存区域

C++ 程序运行时使用的内存区域

# 四个存储类型

变量的存储类型是变量在内存中存储的方式，根据变量的存储类型，可以知道变量的作用域和生存期。
4 个存储类型，分别是 auto （自动类）， register （寄存器类）， static （静态类）和 extern （外部类）。

在 c++ 中定义一个变量的完整形式是：

<存储类型> <数据类型> <变量名>;

# 自动变量 - 用 auto 修饰

用 auto 修饰，默认的定义方式

如：定义一个局部变量 i。
auto int i; 与 int i; 是相同的。

# 寄存器变量 - 用 register 修饰

将尽可能存放在 CPU 的寄存器中，以提高程序的运行效率。

注意，仅局部变量和形参可作为寄存器变量。

# 静态变量 - 用 static 修饰

• 静态变量分配在全局数据区中，定义时系统将提供默认的初始值。

• 静态变量在编译时分配存储空间，在整个程序执行结束后释放存储空间。所以，静态变量具有全局生命期。

• 根据声明的位置不同，静态变量又分为静态局部变量和静态全局变量。

• 静态局部变量是在 “块” 中定义的静态变量。它具有局部作用域，却有全局生命期。在 “块” 执行结束后，该静态局部变量并不释放（其值依旧存在），以便下次调用时可继续使用。

# 外部变量 - 用 extern 修饰

如果在一个源文件中定义的全局变量要在其它源文件中使用，则在使用前应该用 extern 进行声明，表示该全局变量不是在本文件中定义的。

例如：在 1.cpp 文件中定义全局变量
int Dimension=100;
如果在 2.cpp 文件中使用，这时，应在 2.cpp 文件中声明
如下：
extern int Dimension;

静态全局变量：
全局变量可以在其它源文件中使用。
如果在全局变量前加上 static 修饰符，则成为静态全局变量。静态全局变量只能在本文件中使用。

# 例子：函数调用计数器。

使用静态局部变量统计某个函数被调用的次数。

void fun()

{

	static int n=0; // 局部静态变量

	n++;

	cout<<"本函数被调用了"<<n<<"次"<<endl;

}

int main() {

	int i;

	for(i=1;i<=3;i++) {

		fun();

	}

	fun();

	return 0;

}

// 结果 1 2 3 4

如果将函数 fun 中语句 static int n=0; 更改为 int n=0; ，程序的运行结果有何变化？

void fun()

{

	int n=0; // 自动变量

	n++;

	cout<<"本函数被调用了"<<n<<"次"<<endl;

}

int main() {

	int i;

	for(i=1;i<=3;i++) {

		fun();

	}

	fun();

	return 0;

}

// 结果 1 1 1 1

# 课堂讨论

1. 编写递归函数，要考虑哪些关键问题？

包含该函数本身（即递归公式）；需有终止条件。

2. 还有哪些问题可以用递归的方法求解？

斐波那契数列、超时问题、高斯求和也可用递归函数解决。

3. 什么是函数重载，说说函数重载的好处？

函数重载是一个同名函数完成不同的功能，编译系统在编译阶段通过函数参数个数、参数类型不同，函数的返回值来区分该调用哪一个函数，即实现的是静态的多态性。
好处：重载函数通常用来命名一组功能相似的函数，这样做减少了函数名的数量，避免了名字空间的污染，对于程序的可读性有很大的好处。当函数的编写者充分考虑了不同情况下应该运行稍有不同的函数，函数的使用者就不必为这些小细节而烦恼了。

# 随堂练习

1. 递归函数是 。

   • 使用了递推公式的函数
   • 直接或间接调用自己的函数
   • 使用了无限循环的函数
   • 具有返回值的函数

2. 内联函数是 。

   • 在函数中定义的函数
   • 定义或声明时，在返回值类型前使用了 const 关键字的函数了
   • 定义或声明时，在返回值类型前使用了 static 关键字的函数了
   • 定义或声明时，在返回值类型前使用了 inline 关键字的函数

3. 有函数的声明

   void f(int a[],int n);

   下列哪个函数的声明不能构成该函数的重载。

   • int f(int a[],int n);
   • void f(int a[]);
   • int f(int a, int b, int c);
   • void f(char a[],int n);

4. 关于函数的重载，下列哪个说法是正确的？

   • 函数名相同的函数构成重载
   • 参数个数不同的函数构成重载
   • 参数类型不同的函数构成重载
   • 函数名相同，而参数的个数或参数的类型不同的函数构成重载

5. 下列程序的执行结果是 。

   	int f(int &a)
   	{
   	int b=0;
   	static int c=3;
   	b++;
   	c++；
   	return (a+b+c);
   	}
   	int main()
   	{
   	int a=2,i;
   	for(i=0;i<3;i++) {
   	cout<<f(a);
   	}
   	}

   • 7 7 7
   • 7 8 9
   • 7 9 11
   • 7 10 13