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

胡光

你好，我是胡光，今天我们正式开始“编码能力训练篇”的学习。
这里给你一个建议，在刚刚完成了语言基础篇的学习后，我希望你用心地体验“螺旋式上升”的学习过程。就是前面的基础篇虽然学完了，可并不是意味着，不需要再学习更多的语言相关的东西了，你可以做如下两件事情：
对于语言基础，你可以选择学习第二遍，当你站在第一遍的基础上，再回头看的时候，肯定会对之前的知识有更深的理解；
选择在其他参考资料中，继续学习语言中更多的知识点。你会发现，某些之前自己认为晦涩难懂的东西，可以自学搞明白了，这就是我提到的“螺旋式上升”的学习方法。
在接下来的“编码能力训练篇”里，我将着重给你讲解一些编程中的重要技巧。今天呢，我们就从理解循环与递归的编码技巧开始吧！
今日任务循环结构，你已经不陌生了，如下代码所示，是一个单层循环的程序，依次地输出从 1 到 n 的每一个数字，每个数字占一行：
#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        printf("%d\n", i);
    }
    return 0;
}
当我们输入 4 的时候，程序的输出结果如下所示：
1
2
3
4
上面这个是单层循环的情况。下面这个例子，是一个双层循环的例子，每层循环都从 1 循环到 n，循环内部每次输出两个循环遍历的值：
#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d %d\n", i, j);
        }
    }
    return 0;
}
当我们输入 3 的时候，程序的输出结果如下所示：

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文深入浅出地介绍了递归函数在编程中的应用，以及数学归纳法在程序设计中的重要性。首先通过生动的例子解释了递归的概念和过程，强调了递归是一种编程技巧，每一步过程类似但面对的问题规模不同。接着通过具体的代码示例，展示了递归函数的设计和实现，以及如何利用数学归纳法来保证递归函数的正确性。文章还提出了思考题，要求读者将递归程序改成循环程序，并对应数学归纳法的步骤，加深了读者对递归和数学归纳法的理解。最后，文章引出了一个任务，要求完成一个可变循环层数的程序，通过代码框架和完善的代码展示了如何实现这一任务。总的来说，本文通过生动的例子、具体的代码示例和任务，帮助读者理解了递归函数的设计和数学归纳法在程序设计中的重要性，为读者提供了一种理解递归和数学归纳法的方法。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《人人都能学会的编程入门课》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(23)

最新
精选

学写代码的猪
int f1, f2 ; f1 = f2 = 1 ; for(int i = 3; i <n; i++){ f2 = f1 + f2; f1 = f2 - f1; }
作者回复: 完美！
2020-02-13
2
6
Tokamak
老师您好，文章中最后实现的print_loop函数我不能很好的题目的关系对应起来，可以举个例子吗？谢谢老师。
作者回复: 首先，理解递归程序，要理解递归子问题的概念，以及递归问题和子问题之间的同构性，证明递归程序的正确性，是需要利用数学归纳法的。打印五层循环的程序，需要依赖打印四层循环的程序，从4层到5层，这就是数学归纳法中的 k(i) --> k(i+1) 的过程。递归的边界条件中，实现了打印1层循环的程序，这就是数学归纳法的 k(0) 成立，结合在一起，我们就能很轻松的知道，我们所实现的递归程序是否正确。这种思维过程，还需要你在日后的学习中，不断的加强锻炼，以便于你日后能理解和设计出更复杂的递归程序。
2020-05-20

1
Jinlee
斐波那契循环部分： ① int fib(int n) { int f1 = 0, f2 = 1; int i, res; for (i = 1; i <= n; i++){ res = f2; f2 = f1 + f2; f1 = res; } return res; } ② int fib(int n) { int f1 = 0, f2 = 1; int i; for (i = 1; i <= n; i++){ f1, f2 = f2, f1 + f2; } return f1; } 一开始写的代码是②，但是发现输出结果永远是0。这就说明经过for循环之后f1的值并没有改变，这是为什么呢老师？
作者回复: 你应该是学过 python 吧，C 是不支持这种 f1,f2 = f2, f1 + f2 这种语法的。这段代码，在 C 语言中，会被认为是一个逗号表达式，其中包括三个独立的语句，第一个是 f1、第二个是 f2 = f2，第三个是 f1 + f2。
2020-02-13
2
1
罗耀龙@坐忘
茶艺师学编程通过动手把递推程序回归至循环程序，体会到递推以及数学归纳法的便利所在——能用简单的几句话（代码）就把事情搞定了。顺带提一下菲波那契数列，这玩意真的很有趣： 1、明明数列的每一项都是自然数，然而它的通项公式却用无理数来表达； 2、后一项比前一项的比值的极限，就是黄金比例：（√5-1）/2 思考题1： 1、验证边界条件K0成立——> if ( n == 1 || n == 2) return 1 2、假设Ki成立，证明Ki+1也成立——>return fib(n - 1) + fib(n - 2) 3、所有Kn都成立思考题2： /*思考题数组方法 */ #include <stdio.h> #include <stdlib.h> int main(){ printf("此方法产生的斐波那契数列长度等于与数组arr设定的容量大小。\n\n") ; int arr[10] = {1, 1};//设定数组，且第一和第二为“1” int i = 0;//在此环境里，指针移动变量i需要设定在for循环外 for(i = 2; i < 10; i++){//该循环就是按照斐波那契数列的规则填满该数组剩下的空位 arr[i] = arr[i - 1] + arr[i - 2]; } for (i = 0; i < 10; i++){//该循环是，把指针回到一开始，然后按顺序把数组的数字输出 printf(" %d", arr[i]); } printf("\n\n"); system("pause"); return 0; } /*思考题简单方法 */ #include <stdio.h> #include <stdlib.h> int main(){ int a, b, n; printf("请问你要生成多长的裴波那契数列？\n\n"); scanf("%d", &n); a = 1; b = 1; for(int i = 0;i < n; i++){ printf(" %d %d", a, b); a = a + b; b = b + a; } printf("\n\n\n"); system("pause"); return 0; } 附带：课文例子的完整可用版 /*课文例子的完全体*/ #include <stdio.h> int arr[100]; 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; }
作者回复: d(^_^o)，进步神速啊！
2020-06-20


Noya
#include <cstdio> typedef long long ll; int main() { int n; scanf("%d", &n); ll f1 = 1, f2 = 1; if (n == 1 || n == 2) puts("1"); else { for (int i = 3; i <= n; i++) { f2 = f1 + f2; f1 = f2 - f1; } printf("%lld\n", f2); } return 0; }
作者回复: 很不错！能用两个变量搞定 fib 求和的过程！赞！
2020-05-18


王楷程
int arr[100]; int 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"); } for (int i = 1; i <= n; i++) { arr[k] = i; print_loop(k - 1, n, total_k); } return; } 这段代码的return 必须有返回值的吧，而且return 要写在前面，否则，当k == 0时，就会发生越界访问
作者回复: int arr[100]; 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 ; }
2020-03-29


潮汐
作者回复: 你这个程序编译的时候，没有报错？？你试试把 aboutRecursion 以及下面那个 f 函数放到主函数前面去。 -------------- 回复老师：我这个编译是没问题。我把那两个函数搬到main前面也是一样的现象。
作者回复: 哦哦~~~我看到了，你主函数里面，根本就不是在调用 aboutRecursion 函数啊~~~~你是写了一行 aboutRecursion 函数的声明。
2020-03-12


潮汐
老师，有个问题请教： int main() { int aboutRecursion(); } int aboutRecursion() { int n; scanf("%d", &n); printf("%d\n", f(n)); return 0; } int f(int n) { if (n == 1) return 1; return f(n-1) * n; } 我这套代码编译之后运行，并不能按正常的逻辑输入一个n，程序就已经执行完。我尝试将aboutRecursion里的代码主体全部搬到main里，却能正常。请问这是怎么回事呢？
作者回复: 你这个程序编译的时候，没有报错？？你试试把 aboutRecursion 以及下面那个 f 函数放到主函数前面去。
2020-03-09


潮汐
斐波那契数列的思考题 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; } 看了评论，原来可以优化只用两个变量
作者回复: yes！
2020-03-09


宋不肥
老师，能不能把k==0的时候每次输出的一行数认为是k==1的循环的一个元素，把k==1认为是边界条件呀，这样理解可以吗
作者回复: 可以的。
2020-02-18



收起评论