5.函数与递归

一、函数

1.基本介绍

此前我们使用了很多库函数，现在我们可以定义自己的函数来帮助我们完成一些特定的任务。

函数返回值类型 函数名(变量1,变量2,...,变量n)
{
	...
	return;
}
1
2
3
4
5

函数返回值类型有很多类：

• 可以为char,int,double,long long,string等基础数据类型
• 可以为char *，int *, double *等指针类型
• 可以为void表示空，这是唯一不需要返回值的类型
• 可以为自己定义的结构体类型
• 非空类型的函数必须有返回值，但返回值可以不接收

变量类型同样如此，可以为任意类型。

2.定义、声明与使用

函数的定义必须在使用之前，否则编译器将会报错。通常情况下，函数可以以如下方式定义并调用，函数之间也可以来回调用。

int get_dist(int x1,int y1,int x2,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main()
{
    int ans=get_dist(1,2,3,4);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10

但是在某些比较复杂的递归调用中，我们没有办法满足先定义后使用的条件，比如：

void fun1()
{
    fun2();
}
void fun2()
{
    fun1();
}
1
2
3
4
5
6
7
8

面对这种情况，我们可以提前声明函数，就可以不考虑函数执行的先后顺序来写函数了。

• 在声明时注意，不需要写明参数名字，只需写出参数类型即可
• 最后需要添加一个分号;

int fun1(int,int);
char fun2(double,string);
int main()
{
    fun1(1,2);
    
	return 0;
}
int fun1(int a,int b)
{
    fun2(2.1,"123");
}
char fun2(double c,string d)
{
    fun1(1,2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.形参和实参

主函数和myswap函数中都有参数a和b，但因其作用域没有相交，所以可以使用。函数中的局部变量名称也可以和原来变量的名字不同。

如果传递参数时采用如下方式进行，那么两者除了初始值相同外没有任何关系，这就是形参。这样的参数传递过程相当于简单的赋值。

void myswap(int a,int b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
int main()
{
	int a=1,b=2;
	myswap(a,b);
	cout<<a<<" "<<b<<endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在加上取地址符&以后，变成了引用，现在函数中的a和b就和原来主函数的a和b完全一致了，对它做任何操作，最终结果都会反馈到主函数中，这就是实参。这样的参数传递相当于传输了地址，他们可以对对应地址中的元素做操作。

void myswap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
int main()
{
	int a=1,b=2;
	myswap(a,b);
	cout<<a<<" "<<b<<endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

也可以使用$C$语言当中常用的指针类型来完成这一过程：

void myswap(int *a,int *b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
int main()
{
	int a=1,b=2;
	myswap(&a,&b);
	cout<<a<<" "<<b<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.传递数组

根据数组的定义可知，数组名代表的是数组的地址，所以数组的传递也是地址传递，在函数中做任何操作，形同对原变量做相同的操作。

void add_one(int a[])
{
	a[0]++;
    a[1]++;
    a[2]++;
}
int main()
{
	int a[100];
    a[0]=1,a[1]=2,a[2]=3;
	add_one(a);
    cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

也可以使用$C$语言当中常用的指针类型来完成这一过程：

void add_one(int *a)
{
	a[0]++;
    a[1]++;
    a[2]++;
}
int main()
{
	int a[100];
    a[0]=1,a[1]=2,a[2]=3;
	add_one(a);
    cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、递归

1.基本介绍

在程序设计中，递归是一种极其重要的编程思想，它对应的是算法设计中的分治法。

• 将原有的问题分解成一个或者若干个新的，规模比原来更小的子问题。原问题的解可以由子问题的解得到
• 新的子问题时又用到了原有问题相同的解法，可以继续划分出新的子问题
• 以此方法继续分解下去，最后可以得到一个可以直接解出的子问题，此时递归结束
• 逐步返回上一层求解上一级的问题，直到解决原问题

2.分类

根据调用的方式，可以分为直接和间接两种递归方式：

• 间接调用：

  void fun1()
  {
      fun2();
  }
  void fun2()
  {
      fun1();
  }
  1
  2
  3
  4
  5
  6
  7
  8

• 直接调用：

  void fun1()
  {
      fun1();
  }
  1
  2
  3
  4

3.例子：斐波拉契数列

首先根据斐波拉契数列的定义可知，第$n$项$f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=1$。

int Fibonacci(int n)
{
    if(n==1 || n==2)
        return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);
}
1
2
3
4
5
6

记忆化可以大大减少算法所用时间：

int Fibonacci(int n)
{
    if(f[n]!=0)
        return f[n];
    f[n]=Fibonacci(n-1)+Fibonacci(n-2);
    return f[n];
}
1
2
3
4
5
6
7

4.例子：汉诺塔问题

#include 

using namespace std;

void hannuota(char a,char b,char c,int n)//a:起点,b:终点,c:中间,n:圆盘数 
{
    if(n==1)
        cout<<a<<"-->"<<b<<endl;
    else
    {
        hannuota(a,c,b,n-1);
        cout<<a<<"-->"<<b<<endl;
        hannuota(c,b,a,n-1);
    }
}
int main()
{
    int n;
    cin>>n;
    hannuota('A','C','B',n);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、作业

P1255 数楼梯

P1464 Function

P5735 【深基7.例1】距离函数

P5737 【深基7.例3】闰年展示