零基础入门学习C语言008讲：函数（3）

ゞ浴缸里的玫瑰 2022-04-25 00:44 227阅读 0赞

# 8.5 函数的嵌套调用 #

嵌套定义就是在定义一个函数时，其函数体内又包含另一个函数的完整定义。

然而，Ｃ语言不能嵌套定义函数，但可以嵌套调用函数，也就是说，在调用一个函数的过程中，又调用另一个函数。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70][]

### ** 例题**   ###

计算s = 2²! + 3²!（“！” 在高等数学里是阶乘的意思，4！= 4 \* 3 \* 2 \* 1）

思路：

本题可编写两个函数，一个是用来计算平方值的函数square，另一个是用来计算阶乘值的函数factorial。

主函数先调square计算出平方值，再在square中以平方值为实参，调用 factorial计算其阶乘值，然后返回square，再返回主函数，在循环程序中计算累加和。

#include "stdio.h"
    
    int square(int x);
    int factorial(int x);
    
    void main()
    {
    	int sum = 0;
    	for (int i = 2; i < 4; i++)
    	{
    		sum += factorial(square(i));
    	}
    	printf("%d\n", sum);
    }
    
    int factorial(int x)
    {
    	int result = 1;
    	while (x >= 2)
    	{
    		result = result*x;
    		x--;
    	}
    	return result;
    }
    
    int square(int x)
    {
    	return(x*x);
    }

# 8.6 递归递归！！ #

在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。Ｃ语言的特点之一就在于允许函数的递归调用。

例如：

> **ｉｎｔ** **ｆ（int ｘ）**
> 
> **｛**
> 
> **        ｉｎｔ ｙ，ｚ；**
> 
> **        ｚ＝ｆ（ｙ）；**
> 
> **        return（２\*ｚ）；**
> 
> **｝**

说到递归，小甲鱼想到一个古老的故事：

山上有座庙，庙里有个小和尚和一个老和尚，有一天老和尚对小和尚说：“山上有个庙，庙里有个小和尚和一个老和尚，有一天老和尚对小和尚说：“山上有座庙……………………””

**我们可以看出：递归必须要有一个退出的条件！**

### **递归例题**  ###

**用递归的方法求 n!**

求ｎ！也可以用递归方法，即５！等于４！×５，而４！＝３！×４…１！＝１。可用下面的递归公式表示：

**ｎ＝１                      （ｎ＝０，１）**

**ｎ \*（ｎ－１）！          （ｎ＞１）**

#include "stdio.h"
    
    long factorial(int n);
    
    void main()
    {
    	int n;
    	long result;
    	printf("input an interger number:\n");
    	scanf("%d", &n);
    
    	result = factorial(n);
    	printf("%d!=%ld\n", n, result);
    }
    
    long factorial(int n)
    {
    	long temp_result;
    	if (n < 0)
    	{
    		printf("n<0,input error!\n");
    	}
    	else if (n == 0 || n == 1)
    	{
    		temp_result = 1;
    	}
    	else
    	{
    		temp_result = factorial(n - 1)*n;
    	}
    	return temp_result;
    }

### **程序详解** ###

程序中给出的函数factorial()是一个递归函数。主函数调用factorial()后即进入函数factorial()执行。

如果n<0,n==0或n=1时都将结束函数的执行，否则就递归调用ff函数自身。

由于每次递归调用的实参为n-1，即把n-1的值赋予形参n，最后当n-1的值为1时再作递归调用，形参n的值也为1，将使递归终止。然后可逐层退回。

### **注意！！** ###

我们这道例题也可以不用递归的方法来完成。

如可以用迭代法，即从1开始乘以2，再乘以3…直到n。递推法比递归法更容易理解和实现。

递归算法是效率低下的算法！！

但是有些问题则只能用递归算法才能实现。典型的问题是Hanoi塔问题。

### **课后练习题01** ###

Ｈａｎｏｉ（汉诺）塔问题。这是一个古典的数学问题，是一个用递归方法解题的典型例子。问题是这样的：古代有一个梵塔，塔内有3个座A、B、C，开始时Ａ座上有６４个盘子，盘子大小不等，大的在下，小的在上（见图）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70 1][]

有一个老和尚想把这６４个盘子从Ａ座移到Ｃ座，但每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用Ｂ座，要求编程序打印出移动的步骤。

为便于理解，我们先分析将Ａ座上３个盘子移到Ｃ座上的过程：

### **分解** ###

(1) 将Ａ座上２个盘子移到Ｂ座上（借助Ｃ）；

(2) 将Ａ座上１个盘子移到Ｃ座上；

(3) 将Ｂ座上２个盘子移到Ｃ座上（借助Ａ）。

其中第(２)步可以直接实现。第１步又可用递归方法分解为：

１．１ 将Ａ上１个盘子从Ａ移到Ｃ；

１．２ 将Ａ上１个盘子从Ａ移到Ｂ；

１．３ 将Ｃ上１个盘子从Ｃ移到Ｂ。

第(３)步可以分解为：

３．１ 将Ｂ上１个盘子从Ｂ移到Ａ上；

３．２ 将Ｂ上１个盘子从Ｂ移到Ｃ上；

３．３ 将Ａ上１个盘子从Ａ移到Ｃ上。

将以上综合起来，可得到移动3个盘子的步骤为

Ａ→Ｃ，Ａ→Ｂ，Ｃ→Ｂ，Ａ→Ｃ，Ｂ→Ａ，Ｂ→Ｃ，Ａ→Ｃ。

由上面的分析可知：将ｎ个盘子从Ａ座移到Ｃ座可以分解为以下3个步骤：

(1) 将Ａ上ｎ－１个盘借助Ｃ座先移到Ｂ座上。

(2) 把Ａ座上剩下的一个盘移到Ｃ座上。

(3) 将ｎ－１个盘从Ｂ座借助于Ａ座移到Ｃ座上。

#include "stdio.h"
    
    void hanoi(int n, char one, char two, char three);
    
    void main()
    {
    	int n;
    	char A = 'A', B = 'B', C = 'C';
    	printf("input number of pie:\n");
    	scanf("%d", &n);
    	hanoi(n, A, B, C);
    }
    
    void hanoi(int n, char one, char two, char three)
    /*  定义hanoi函数,将ｎ个盘从one座借助two座，移到three座 */
    {
    	void move(char x, char y);     /* 对move函数的声明 */
    	if (n == 1)
    	{
    		move(one, three);
    	}
    	else
    	{
    		hanoi(n - 1, one, three, two);
    		move(one, three);
    		hanoi(n - 1, two, one, three);
    	}
    }
    void move(char x, char y)           /*  定义move函数 */
    {
    	printf("%c-->%c\n", x, y);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70]: /images/20220210/38f3f22376f44456bd1d8b5940fa577e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70 1]: /images/20220210/8b56b16cf7be4180bdf46285360a06cd.png