C函数与递归

WuShF

发布于 2023-03-08 09:47:45

4380

发布于 2023-03-08 09:47:45

文章被收录于专栏：笔记分享

函数的特性及定义

在编程语言中，可以把函数看做一个盒子，这个盒子有如下几个特性：

开始执行时，函数可以被输入一些值
执行过程中，函数可以做一些事情
执行完成后，函数可以返回一些值

函数的写法公式：

函数返回值类型 函数名(函数输入参数值)
{
    做点什么事情
    return 函数返回值;
}

被花括号包括的被称为函数体，注意函数体一定要被花括号包括且不可省略。花括号上面的函数名、函数参数及返回值被称作函数头。

注意每个输入参数必须指明其变量类型，不能省略变量类型。

int add(int a, int b)   //正确
int add(int a, b)       //错误

函数的调用

函数需要被另一个函数调用才能执行。

#include <stdio.h>
int add(int a, int b)
{
	return a + b;
}
int main()
{
	int result;
	result = add(2, 3); // 函数调用
	printf("%d", result);
	return 0;
}

main被称作主调函数，add被称作被调函数。在add函数头中，标明了函数的返回值类型为int，说明这个函数被调用后将返回一个int类型的结果。

为什么要将代码封装成函数?

如果程序需要多次完成某项任务，那么你有两个选择：

将同样的代码复制多份。
将代码封装为一个函数，在需要的地方调用这个函数。

函数返回

#include <stdio.h>
void showStarts()
{
	printf("    *\n");
	printf("   * *\n");
	printf("  * * *\n");
	printf(" * * * *\n");
	printf("* * * * *\n");
}
int main()
{
	showStarts();
	return 0;
}

showStarts 函数将会打印一个星星组成的三角形。这个函数没有输入参数，也不需要返回值。所以，在函数定义时，参数的括号留空。返回值类型为 void ，表示空类型，即没有返回值。可以在函数参数的括号中填上void，明确表示函数不需要参数。可以用return将函数返回主调函数，并带回一个返回值。对于没有返回值的函数，可以省略return。函数运行完花括号内的语句后，就自动结束。 若函数需要返回值，则必须使用return带回一个返回值才能正常通过编译。 return可以出现在函数的任意位置。一旦程序执行到return，就会停止函数的执行，返回主调函数。

函数声明

在一个源文件中，如果函数调用前没有函数定义。那么可以使用函数声明通知编译器，有这个函数存在。 函数声明的写法非常简单：函数头 + 分号函数声明也被称作函数原型。

#include <stdio.h>
#include <math.h>
// 函数调用前加上了函数声明，告诉编译器有这个函数存在
double areaOfTriangle(double a, double b, double c);
int isTriangle(double a, double b, double c);
int main()
{
	double a, b, c;
	scanf("%lf %lf %lf", &a, &b, &c);
	if (isTriangle(a, b, c) == 0)
	{
		printf("Not a triangle\n");
		return 0;
	}
	double s;
	s = areaOfTriangle(a, b, c);
	printf("area of triangle is %f", s);
	return 0;
}
// 函数定义放到了函数调用后
double areaOfTriangle(double a, double b, double c)
{
	double p, s;
	p = (a + b + c) / 2;
	s = sqrt(p * (p - a) * (p - b) * (p - c));
	return s;
}
int isTriangle(double a, double b, double c)
{
	if (a + b > c && a + c > b && b + c > a)
	{
		return 1;
	}
	return 0;
}

编译器读到函数声明后，便可知晓 areaOfTriangle 与 isTriangle 的参数与返回值。在其后的函数调用中，可以根据函数声明的形式，检查参数类型和个数是否传递正确。返回值是否被正常接收。虽然编译器暂时不知道函数里面是如何定义的，但是这对于检查函数调用是否正确已经足够了。

另外，函数声明时可以省略变量名。从这里可以看出，参数变量名对于函数声明来说并不重要，即使函数声明使用与函数定义不一样的参数变量名，也是可以的。

double areaOfTriangle(double a, double b, double c);
int isTriangle(double a, double b, double c);
// 省略参数变量名
double areaOfTriangle(double, double, double);
int isTriangle(double, double, double);
// 乱写参数变量名
double areaOfTriangle(double xsie, double sgrb, double xvdc);
int isTriangle(double aooj, double bngb, double vfhfc);

参数与返回值的类型自动转换

#include <stdio.h>
int add(int a, int b)
{
	return a + b;
}
int main()
{
	int result;
	result = add(2, 3); // 函数调用
	printf("%d", result);
	return 0;
}

add函数参数列表中的a，b被称作形式参数，简称形参。它指代函数参数的类型，以及参数进入add后，需要经历的处理步骤，没有确定值。而在函数调用中add(2, 3)的2,3被称作实际参数，简称实参。它们将确定形式参数的值具体是什么。

参数的自动转换

形式参数与实际参数的类型允许不一致的情况。

#include <stdio.h>
int add(int a, int b)
{
	return a + b;
}
int main()
{
	int result;
	result = add(2.2, 3.3); // 函数调用
	printf("%d", result);
	return 0;
}

编译出现了两个警告，告诉我们double到int的转换会丢失数据，并且最后的结果为5。将实际参数 2.2，3.3 传递给形式参数 int a, int b 时，编译器会尝试将实参转换为形参的类型。若可以转换，那么将编译通过。若转换过程中可能出现数据丢失，将以警告的形式告诉程序员。 2.2，3.3 被转换为了整型 2，3 ，小数部分被丢失。若无法转换，那么编译失败。

返回值的自动转换

#include <stdio.h>
double add(int a, int b)
{
	return a + b;
}
int main()
{
	double result;
	result = add(2, 3); // 函数调用
	printf("%f", result);
	return 0;
}

现在我们把返回值改为了double类型。但是，参数仍然保持int类型。 a与b相加的结果为int类型，返回时，会尝试将int转换为double。int可以被转换为double，所以编译通过。

形参与实参相互独立

#include <stdio.h>
void swap(int a, int b)
{
	int temp = a;
	a = b;
	b = temp;
}
int main()
{
	int a, b;
	int temp;
	a = 1;
	b = 2;
	printf("a=%d b=%d\n", a, b);
	// 交换a，b变量
	swap(a, b);
	printf("a=%d b=%d\n", a, b);
	return 0;
}

交换失败

a=1 b=2
a=1 b=2

虽然主函数中的变量a，b与函数中的形式参数a，b变量名相同。但是，它们却是相互独立的变量。调用 swap 函数并传参时，是将主函数中变量a，b的值，传递给形式参数a，b。

不同函数内的变量相互独立

#include <stdio.h>
void func()
{
	int a;
	a = 100;
	printf("a in func %d\n", a);
}
int main()
{
	int a = 0;
	printf("a in main %d\n", a);
	func();
	printf("a in main %d\n", a);
	return 0;
}

从结果中可以看出，这两个变量虽然变量名相同，但是却是两个互相独立的变量。

a in main 0
a in func 100
a in main 0

若去掉 func 函数中的变量声明，那么编译器将无法识别a标识符。 函数内声明的变量为局部变量，不同函数内的局部变量相互独立。 如果你想让一个局部变量的值在另一个函数中使用，可以把它当做一个参数，传递其值到另一个函数中。

函数递归调用

#include <stdio.h>
void func(int n)
{
    printf("%d\n", n);
    func(n + 1);
}
int main()
{
    func(0);
    return 0;
}

编译可以通过，运行依次打印出了0,1,2,3,4,5… 在C语言中，在一个函数内部是可以再次调用自己的。这种调用被称之为函数递归。由于函数func首尾相接，它将造成程序陷入死循环。就像一条蛇，咬住了自己的尾巴，整个蛇构成了一个环形。如果程序陷入了循环，请使用Ctrl + C组合键结束程序如果不打断程序执行，那么过不了多久，程序将出现栈溢出异常，导致程序异常结束。

如何正确地进行递归？

递归函数的两个要素：

递推规则
递推结束条件

现在我们给程序加上递推结束条件，当n为5时，就让递推结束。

#include <stdio.h>
void func(int n)
{
    if (n == 5)
        return;
    printf("%d\n", n);
    func(n + 1);
}
int main()
{
    func(0);
    return 0;
}

流程在n小于5之前，一直递推至下级函数。当n为5时，从下级函数开始回归

递推与回归

#include <stdio.h>
void func(int n)
{
    if (n == 5)
        return;
    printf("after %d\n", n);
    func(n + 1);
    printf("before %d\n", n);
}
int main()
{
    func(0);
    return 0;
}

输出结果

after 0
after 1
after 2
after 3
after 4
before 4
before 3
before 2
before 1
before 0

标号为1,2,3,4,5的printf在递推过程中，被依次执行。而标号为6,7,8,9,10的printf，必须等到回归过程，才会被执行到。由于回归过程与递推过程是逆向的，所以，输出的n值是逆序的。对于此func函数，放在递归调用前的语句将在递推过程中执行。而放在递归调用后的语句将在回归过程中执行。

使用递归计算阶乘

规律如下：

当n为1或0时，n的阶乘为1。
当n大于1时，n的阶乘为n * (n - 1)!

那么假设有这么一个函数f(n)，这个函数传入一个整数n，返回n的阶乘n!。

当n为1或0时，f(n)返回1。
当n大于1时，f(n) = n * f(n - 1)

写出如下代码。

#include <stdio.h>
int f(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    return n * f(n - 1);
}
int main()
{
    int result = f(4);
    printf("%d\n", result);
    return 0;
}

递推流程中，可以确定当前的n分别为4,3,2,1。接着进入了递归调用f(n - 1)，直到n为1时，开始回归。回归到n为2时，计算2 * 1。回归到n为3时，计算3 _ (2 _ 1)。回归到n为4时，计算4 _ (3 _ 2 * 1)。

使用递归计算斐波那契数列

斐波那契数列，第1、2项分别为1，之后每一项为前两项相加之和那么假设有这么一个函数f(n)，这个函数传入一个整数n，返回斐波那契数列的第n项。

当n为1或2时，f(n)返回1。
当n大于2时，f(n) = f(n - 1) + f(n - 2)。

#include <stdio.h>
int f(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}
int main()
{
    int result = f(4);
    printf("%d\n", result);
    return 0;
}