数学归纳法：搞定循环与递归的钥匙

任务

实现一个可变循环层数的程序。

编码

我们可以一开始假设，有一个函数，是实现 5 层循环打印的程序，那么它会循环 n 次，每次调用一个实现 4 层循环打印的程序。

//代码框架
int print_loop(int k, int n) {
    //代表 k 层循环的程序，然后循环 n 次，每次调用一个 k - 1 层循环的程序。
    if (k == 0) {
        // 打印一行
    }
    for (int i = 1; i <= n; i++) {
        print_loop(k - 1, n);
    }
    return;
}

完善程序

int arr[100];
/*
入参：
total_k，代表了一共有多少层循环，这个参数是为了方便我们最后确定循环输出的上界
*/
void print_loop(int k, int n, int total_k) {
    if (k == 0) {
        for (int i = total_k; i >= 1; i--) {
            if (i != total_k) printf(" ");
            printf("%d", arr[i]);
        }
        printf("\n");
        return ;
    }
    for (int i = 1; i <= n; i++) {
        arr[k] = i;
        print_loop(k - 1, n, total_k);
    }
    return ;
}

思考题

#include <stdio.h>

int fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);  
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}

上面这段程序中，fib 函数是求菲波那契数列第 n 项值的函数。菲波那契数列的定义如下：

根据如上内容，你需要完成两个小的思考题：

1，请将上述菲波那契数列求解的程序从递归程序，改成循环程序。

int fib(n) {
    // 递归写法
    /*
        if (n == 1 || n == 2) return 1; // 终止条件 -- 数学归纳法step1
        return fib(n-1) + fib(n-2); // 处理过程 -- 数学归纳法step2
    */

    // 循环写法
    int f1 = 1, f2 = 1, f3;
    for (int i = 3; i <= n; i++) {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
    }
    return f3;
}

2，请将上述递归程序的代码和数学归纳法中的步骤做一一对应。

#include <stdio.h>

int fib(int n) {
    if (n == 1 || n == 2) return 1;  //数学归纳法中所谓的 k0​ 成立，这一步保证了，fib 函数计算的第 1 项 和 第 2 项的斐波那契函数值一定是正确的。
    return fib(n - 1) + fib(n - 2);  //数学归纳法中的第二步，假设 ki​ 成立，证明 ki+1​ 也成立。
    //最后结论，这个fib 递归函数设计是正确的。
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}

小结

• 数学归纳法中重要的两部分，一是要边界条件成立，二是证明转移过程成立。
• 程序设计最重要的是正确性，递归函数的正确性可以利用数学归纳法来保证。
• 递归程序设计中的重要的两部分：边界条件和处理过程。所谓边界条件，就是当递归函数中的参数等于多少的时候，可以直接返回的条件。处理过程呢，就是设计程序过程，处理递归调用的返回结果，根据递归调用的返回结果，得到本函数的结果。