C语言函数嵌套与递归调用-学习十八

函数的嵌套调用

C语言的函数定义是互相平行、独立的即函数不能嵌套定义，但可以嵌套调用函数。
即调用一个函数的过程中，又可以调用另一个函数。

上图表示了两层嵌套的情形。
- 其执行过程是:
- 1.执行 main函数 中调用 a函数 的语句时，即转去执行a函数;
- 2.在 a函数 中调用 b函数 时,又转去执行 b函数;
- 3.在 b函数 执行完毕返回 a函数 的断点继续执行;
- 4.在 a函数 执行完毕返回 main函数 的断点继续执行。
例如：

输入4个整数，找出其中最大的数。用函数的嵌套调用来处理。

#include <stdio.h>

main() {
    int n1, n2, n3, n4,max;
    int max4(int a, int b, int c, int d);

    printf("请输入4个整数：\n");
    scanf_s("%d %d %d %d", &n1, &n2, &n3, &n4);
    max = max4(n1, n2, n3, n4);
    printf("max = %d\n", max);

}

int max4(int a, int b, int c, int d) {
    int max2(int a, int b);
    int m;
    m = max2(a, b);
    m = max2(m, c);
    m = max2(m, d);
    return m;
}

int max2(int a,int b){
        return  (a > b ? a : b);
}

函数的递归调用

在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。

绘图1.png

应使用if语句控制结束调用
例如：

a1 = 10, a2 = a1 +2, a3 = a2+2，以此类推求a36的值。

#include <stdio.h>

main() {
    int add(int a);

    printf("a36 = %d\n", add(36));
}

int add(int a) {
    int sum;
    if (a == 1) {
        sum = 10;
    }
    else {
        sum = add(a-1) + 2;
    }
    return sum;
}

例子

用递归方法求n!

#include <stdio.h>

main() {
    int n;
    int rec(int a);
    printf("输入n的值：");
    scanf_s("%d", &n);

    printf("%d的阶乘 = %d\n",n, rec(n));
}

int rec(int a) {
    int x;
    if (a == 1) {
        x = 1;
    }
    else {
        x = rec(a-1) * a;
    }
    return x;
}

猴子吃桃问题:猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘了多少个桃子。

#include <stdio.h>

main() {
    int n;
    int toatal(int a);
    n = toatal(1);
    printf("总数 = %d\n",n);
}

int toatal(int day) {
    int x;
    if (day == 10) {
        x = 1 ;
    }
    else { 
        x = (toatal(day + 1) + 1) * 2 ;  // 反向思维理解，程序必须有确定值才能进行计算
    }                                               //所以程序会先从有确定值的第10天开始从里向外计算
    return x;
}

汉诺（Hanoi）塔问题，古代某寺庙中有一个梵塔，塔内有3个座A、B和C，座A上放着64个大小不等的盘，其中大盘在下，小盘在上。有一个和尚想把这64 个盘从座A搬到座C，但一次只能搬一个盘，搬动的盘只允许放在其他两个座上，且大盘不能压在小盘上，移动过程可以使用B座。编写函数输出移动盘子的步骤。

解题思路：
- 1.将A上n-1个盘借助C座先移到B座上；
- 2.把A座上剩下的一个盘移到c座上；
- 3.将n-1个盘从B座借助于A座移到C座上。
- 关键步骤图解

#include <stdio.h>

main() {
    int m;
    void hanoi(int n, char A, char B, char C);
    
    printf("输入盘子的数量：\n");
    scanf_s("%d", &m);
    hanoi(m, 'A', 'B', 'C');
}

void hanoi(int n,char A,char B, char C) {
    void move(char x,char y);
    if (n == 1) {
        move(A, C);
    }
    else {
        hanoi(n - 1, A, C, B);
        move(A, C);
        hanoi(n - 1, B, A, C);
    }
}

void move(char x, char y) {
    printf("%c ==> %c\n", x, y);
}