程序员经验分享-hwhale

关于递归问题的一点见解

2023-05-16

背景

       前不久参加牛客网的有书共读活动意外的获得了一本《具体数学》，对此感谢牛客。其次领书是要条件的，条件就是写读书笔记。搞ACM的都知道具体数学是本什么样的神书（也可能是我太弱了），不过没办法，规则要写那就要写，好在第一章讲递归，还在我的承受范围之内。

正文

什么是递归

既然是讲递归那么我们首先就要明白一件事，那就是什么是递归。

递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。[1]

这是维基百科对于递归的非正式定义，我深以为然。但是对于没有接触过的人来说可能比较抽象，下面我来举个例子

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”[2]

大家看了这个例子是不是清晰了很多，这就是递归（个人认为这比上面的定义好多了，如果不是科学要严谨的话，完全可以用它来替代那乏味的定义）

递归问题有什么特征

这个问题也可以反过来，就是我们是根据什么特征来判断一个问题是否是递归问题的

《具体数学》在最开始的地方提到，每一个问题的解都依赖于统一的问题的更小实例的解[3]。我们再来举例分析、

求解n的阶乘，首先我们要求n-1的阶乘然后在乘以n，这就是每一个问题都依赖于更小实例解的体现。换言之，当我们求问题规模为n的问题时，我们必须知道规模为n-1的问题的解。我们把具备这个特征的问题叫做递归问题

如何使用编程语言解决递归问题

这里以C语言为例

在大多数编程语言当中都允许函数自己调用自己，在计算机科学中，我们把这一现象叫做递归

下面我们来解决计算n的阶乘问题

按上面所说的，我们不断的缩小数据规模就可以了，但是还有一个问题，那就是什么时候终止。因为理论上函数是可以不断的调用自己的，数据规模也可以不断的减少（理论上可以一直逼近负无穷）

不知大家注意到了没有我这里是说的都是理论上，那么实际上呢？

实际上计算机的资源是有限的，它不能一直重复一个工作，例如，int的范围是-2147483648~2147483647，当你的计算机运行到-2147483648时，在进行运算就会产生溢出，所以你计算机无法正常（这里的正常是指按程序的意图工作）工作；在比如，函数的调用是通过一个叫做调用栈（Call Statck）的栈来完成的。当你 的程序递归到一定程度时，栈就会满了，此时继续递归调用会爆栈，程序会非正常终止（不信的同学可以试一试，看看非正常终止的程序和正常终止的程序返回值有什么区别，codeblocks调试时最后会输出返回值）

说点题外话，人其实也是不能一直（或者说无间断的）重复同一个工作的，因为人总要吃饭，总要喝水，总要睡觉。人只可以在某个时间段内重复同一个工作，从这里看（只考虑持续工作时间）同一件事情用机器做要比用人做合适多了，因为机器只要电量充足，程序正确，机器可以持续工作的时间要远大于人类。所以那些懒惰的人还是请尽快学些有用的东西吧。AI的风会刮到哪没有人会知道，等到AI全部替换底层工人时在转行已经迟了。推荐看一下李开复的《人工智能》，算是科普文吧。

上面的内容可能有点偏题，我们再回到原来的问题，即递归问题除了要写递归式还要写什么？答案是终止条件，我们必须告诉计算机什么时候终止，否则就会发生我刚才提到的问题，如果是程序设计竞赛或一些认证考试的话，缺少（不是没有）终止条件也有可能会使你的程序运行时间过长从而导致超时而使得你不得分

因此在设计递归函数时我们不得不考虑两个问题，一个是递归式，一个终止条件。

以下给出解决n！问题的参考代码

#include <stdio.h>

int f(int n) {
    if (n == 1 || n == 0) return 1;   //终止条件
    return f(n - 1) * n;   //递归式
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        printf("%d\n", f(n));
    }
    return 0;
}

大家觉得上面的代码怎么样？很好吗？

很好你就错了，虽然我们求阶乘时都是输入一个非负整数，但是你并不能保证输入数据都是负数 你不能避免奇葩客户，所以当你输入-1时程序就会崩溃，如图

我们的程序应当具有良好的鲁棒性，所以我们应当预先判断非法数据

改进后的代码如下

#include <stdio.h>

int f(int n) {
    if (n == 1 || n == 0) return 1;   //终止条件
    return f(n - 1) * n;   //递归式
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n < 0) puts("您输入的数据非法，请重新输入");
        else printf("%d\n", f(n));
    }
    return 0;
}

递归问题的递推实现

递归问题其实可以用递推实现，关于递归与递推的区别可以看一下知乎的一篇讨论, 递推和递归的区别是什么？[4]

同样是刚才那个问题，我给出它的递推实现（假设所有的同学都会递推）

#include <stdio.h>

#define N 550

int dp[N];

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n < 0) puts("您输入的数据非法，请重新输入");
        else {
            int i;
            dp[0] = dp[1] = 1;
            for (i = 2; i <= n; ++i) dp[i] = dp[i - 1] * i;
            printf("%d\n", dp[n]);
        }
    }
    return 0;
}

上面的代码可以通过一个预处理来优化，因为讲的是递归所以在这里不进行讲解，有兴趣的同学可以私聊我

大家可以看到我们仅仅通过一个for循环而不用函数自调就完成了计算过程，所以我们不用隐式的调用栈，从这里讲递推的效率比递归要高。但是有一些问题又特别适合用递归（原谅我没有找到例子，找到的同学可以私聊我），我们就必须适用递归。这种性质在动态规划中得到了充分体现，就我个人而言，出于效率考虑比较倾向于递推，但一些比较复杂的问题比较喜欢用递归，因为简单直观

编程实战

因为题目描述过长，所以我在这里仅给出题目链接，分析和参考代码

 例题1 蟠桃记

解法一：设 t(n)代表天数为n时的答案，则当n = 1时，t(1) = 1; 这一点很重要，它是边界条件

其次，一天吃一半多一点，也就是剩下的加 1 恰好是吃之前的一半，因此 t(n) = (t(n - 1) + 1) * 2;  这也很重要，它是递归式

有了递归式和终止条件我们不难写出如下代码

#include <stdio.h>

int t(int n) {
    if (n == 1) return 1;
    return (t(n - 1) + 1) * 2;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        printf("%d\n", t(n));
    }
    return 0;
}

解法二

我们把前10项列出来，是下面这个样子的

找规律可得t(n) = 3 * 2 ^(n - 1) - 2

规律很难找怎么办？没有关系，我们可以借助一个叫做OEIS的网站帮助我们完成这项工作，虽然有种作弊的感觉

参考代码

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int tmp = pow(2, n - 1);   //记录2 ^ (n - 1)
        printf("%d\n", 3 * tmp - 2);
    }
    return 0;
}

例题二 母牛的故事

分析：和斐波那契数列差不多。把前5项写下来可以发现规律f(n) = f(n - 1) + f(n - 3) ，其中，边界条件是f(0) = f(1) = 1; f(2) = 2; f(3) = 3; f(4) = 4; 

参考代码

#include <stdio.h>
#include <math.h>

#define N 110

int dp[N];

int main() {
    int n;
    dp[0] = dp[1] = 1; dp[2] = 2; dp[3] = 3;
    for (int i = 4; i <= 55; ++i) dp[i] = dp[i - 3] + dp[i - 1];
    while (scanf("%d", &n) != EOF && n) {
        printf("%d\n", dp[n]);
    }
    return 0;
}

例题三大数阶乘

这个题用到了java中的BigInteger，如果有不会用java的同学可以参考这篇博客https://blog.csdn.net/DongChengRong/article/details/78848399

分析：因为m很小只有5000所以我们可以从1开始打一个阶乘表，这样的话当有输入的时候我们就可以用O(1)的复杂度解决它
参考代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        BigInteger f[] = new BigInteger[5500];
        f[0] = f[1] = BigInteger.ONE;
        for (int i = 2; i <= 5000; ++i) {
            f[i] = f[i - 1].multiply(BigInteger.valueOf(i));
        }
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            int m = cin.nextInt();
            System.out.println(f[m]);
        }
    }
}

 

参考文献

[1]https://zh.wikipedia.org/wiki/%E9%80%92%E5%BD%92

[2]https://zh.wikipedia.org/wiki/%E9%80%92%E5%BD%92#%E8%AF%AD%E8%A8%80%E4%BE%8B%E5%AD%90

[3]Ronald L.Graham; Donald E.Knuth; Oren Patashnik. 具体数学 计算机科学基础（第二版） 人民邮电出版社 .2018. ISBN 978-7-115-30810-8

[4] https://www.zhihu.com/question/20651054

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

关于递归问题的一点见解 的相关文章

  • Android studio错误修复快捷建

    用Android studio有的时候他报错却不给修复提示 xff0c 我们该怎么办呢 xff1f 当然是借助快捷键了 xff01 把光标移到出错的地方 xff0c 按下Alt 43 Enter就可以了 ps 摁一下就可以 xff0c 不要

  • Android老师作业七

    历经千辛万苦终于把它跑了出来 xff0c 截图如下 遇到问题如下 一 Android studio乱码 xff1a http blog csdn net dongchengrong article details 72594233 二 自定

  • The requested resource is not available

    具体问题截图 原因 xff1a 请求资源不合适 就拿我这个来说 xff0c 只要把jnp的扩展名改成jpg就好了

  • uva12100解题报告

    水题留念 一个队列模拟进出操作 xff0c 一个优先队列保存优先级 xff0c 模拟过程输出结果 Time 0ms include lt cstdio gt include lt queue gt include lt cstring gt

  • android studio删除jar包后报错

    我是把某个jar包删了又加的一个新的 xff0c 结果显示有个目录没找到 xff0c 如下 这是因为没有正确的删除jar包导致的 xff0c 正确的删除方式如下

  • 小米笔记本、小米游戏本重装原装出厂镜像教程-有百度盘的提取码

    转 xff1a 新的干货儿 小米笔记本 小米游戏本重装原装出厂镜像教程 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61

  • UVA232解题报告

    注意一个地方 xff0c 编号是从左到右 从上往下增大的 xff0c 所以我们可以从这里做文章按照编号大小的顺序遍历输出 实际上 xff0c 因为给出的数据范围很小我们的求解速度还是很快的 xff0c 尤其是横向输出时还可以做点小手脚加快运

  • 较好的程序设计竞赛有哪些

    一 含金量最高 最出名的ACM ICPC xff1a https icpc baylor edu 二 百度的百度之星 xff1a http star baidu com 官微 xff1a http weibo com baiduastar

  • c++ string比较大小

    很简单 xff0c 像整型一样直接比较 例如 xff1a include lt iostream gt include lt string gt using namespace std int main string a 61 34 abc

  • UVA230解题报告

    这个题耗了我六天时间 xff0c 很打击我对算法的学习 xff0c 不过 xff0c 我终于解决了他 分析如下 仔细观察我们可以发现后面的操作与输出都是围绕标题 xff08 title xff09 展开的 xff0c 作者 xff08 au

  • hibernate数据修改后不能及时更新

    错误描述 使用hibernate更新或者插入数据后明明数据库中保存进去了但是查出来的结果还是以前的 解决方案 在查询之前调用session clear 清理缓存

  • 经典不定积分题解

  • Android老师作业八

    一 xff1a 第一条广播 第二条广播 xff08 因为第一条广播的优先级比第二条广播的优先级高 xff09 二 第一条广播 第二条广播 xff08 因为第一条广播注册的顺序比第二条广播注册的顺序靠前 xff09 三 第一条广播 广播被我拦

  • 用散列表实现输入拼音输出大写英文字母的功能

    我本来是想实现输入拼音输出汉字的功能 xff0c 可是 xff0c 好像是因为C语言只能识别256个ASCII码 xff0c 所以出现了乱码现象 xff0c 所以我不得已把汉字改成了大写英文字母 实现的关键是哈希函数 xff0c 这里因为我

  • hibernate增删改查

    package cn gov test import java util Set import cn gov entity Address import cn gov entity Person import cn gov factory

  • 如何报名计算机等级考试

    只限山东考生 进入http www sdzk cn zsks index shtm如图 xff0c 点击全国计算机等级考试 进入下图网页 xff0c 选择你要考试的城市 注册一个账号或登录 选择当前场次 选择同意 填写个人信息 xff0c

  • bootstrapvalidator实现校验、校验清除重置

    问题 xff1a 经常开发中用到modal对话框弹出验证以后第二次弹框时上次的验证效果依然有效 xff0c 那就要想办法第二次弹框之前去掉上次的验证 xff1b 解决办法 xff1a 1 引入bootstrap的validator的校验js

  • ACM题目分类

    基本算法 模拟题 xff1a UVA118 递推 xff1a 勘测 位运算 xff1a Sum AND Subarrays 快速幂 xff1a dreamstart的催促 动态规划 xff1a LCS xff1a UVA10192 动态规划

  • 简单选择排序

    与冒泡排序相反 xff0c 每次把最小的 xff08 升序 xff09 放到第一个 xff0c 共放置n 1次 include lt stdio h gt void sort int A int N for int i 61 0 i lt

  • 二叉查找树练习代码

    include lt stdio h gt include lt stdlib h gt define Element int typedef struct Node Element data struct Node left right

随机推荐

  • ncre不能支付

    NCRE支付的时候点击支付按钮没反应 xff0c 这是怎么回事 xff1f 这是因为浏览器把它当成垃圾网站给拦截了 xff0c 你可以换个浏览器也可以找找有没有被阻止的网页 我用的是Google的Chrome xff0c 以它为例示范一下

  • 插入排序练习代码

    include lt stdio h gt void sort int A int n int i j tmp for i 61 1 i lt n i 43 43 tmp 61 A i for j 61 i j gt 0 j if tmp

  • 希尔排序练习代码

    include lt stdio h gt void sort int A int n int i j tmp increment for increment 61 n 2 increment gt 0 increment 61 2 for

  • 二叉树、树、森林之间的转化

    树转二叉树 将孩子作为左孩子 xff0c 将第一个兄弟作为右孩子 二叉树转树 将左孩子的右孩子作为自己的孩子 森林转二叉树 与转树差不多 xff0c 唯一需要注意的是要把第二棵树的根节点作为第一棵树的一个兄弟 二叉树转森林 把右孩子断开成一

  • 最小堆练习代码

    include lt stdio h gt include lt stdlib h gt define INF 100000 define MinData 10 typedef int Element typedef struct Node

  • 不带头结点的单链表逆置操作

    reverse函数负责逆置工作 include lt stdio h gt include lt stdlib h gt typedef struct Node int data struct Node next Node List voi

  • 我的第一个Python程序

    突然想学Python了 xff0c 今天开始学习 xff0c 编出了我的第一个Python程序 calculate the area and circumference of a circle from its radius import

  • PowerShell-压缩解压缩文件

    PowerShell 压缩解压缩文件 缘起压缩文件1 调用第三方工具自带命令2 PowerShell命令压缩 解压缩文件1 PS命令解压2 Windows内置解压3 调用COM对象 附 xff1a 查看PowerShell版本方法 缘起 前

  • Python绘制五角星

    借用了turtle这一模块的帮助 import turtle turtle forward 100 turtle right 144 turtle forward 100 turtle right 144 turtle forward 10

  • 小明的调查作业(南阳理工OJ48)

    描述 小明的老师布置了一份调查作业 xff0c 小明想在学校中请一些同学一起做一项问卷调查 xff0c 聪明的小明为了实验的客观性 xff0c 想利用自己的计算机知识帮助自己 他先用计算机生成了N个1到1000之间的随机整数 xff08 0

  • 如何加快cin\cout读取数据的速度

    在使用cin cout前加上 ios sync with stdio false 这可以加快读取数据的速度 xff0c 但是有一个非常不好的副作用就是不能与scanf这类的输入输出方法混用了 xff0c 我就是因为混用结果有一个题提交了10

  • Python读写文件

    coding utf 8 向指定文件中存储指定内容 def text create name msg full path 61 name 43 39 txt 39 file 61 open full path 39 w 39 file wr

  • eclipse设置编码格式

    打开文件 xff0c 点击edit下的setCoding 如图 弹出一个对话框 xff0c 点击other 选择utf 8 先点击apply再点击OK 完成

  • Python打印九九乘法表

    打印九九乘法表 def create table for row in range 1 10 for column in range 1 row 43 1 print str row 43 39 39 43 str column 43 39

  • UVA10562解题报告

    我的GitHub地址 xff1a https github com DongChengrong ACM Program 仔细观察他给出的树 xff0c 我们可以发现这棵多叉树长得比较有特点 最上是树根 xff0c 而每一个节点只要有孩子下面

  • 实用函数之判断素数

    功能 xff1a 判断一个数是否是素数 素数概念 xff1a 只能被1和它本身整除的数 实现语言 xff1a C C 43 43 int is prime int n if n lt 61 1 return 0 int m 61 floor

  • 打不开IDLE

    我开始安装的是Python3 6 xff0c 后来发现很多库不支持3 6只支持2 7 xff0c 所以我又重装了2 7 xff0c 这时再打开IDLE就打不开了 经过我的几次努力终于找到了解决方案 将C盘 用户 xff08 user xff

  • Ubuntu系统中使用gdebi安装.deb文件

    传统软件套件管理工具 dpkg 定义 xff1a dpkg为 Debian 专门开发的套件管理系统 xff0c 方便软件的安装 更新及移除 首先 xff0c 要安装dpkg软件管理工具 suo span class token functi

  • IDLE设置字体大小

    点击option gt Configure 在出现的弹框里修改字体大小 xff0c 注意字体不能是楷体等与中文相关的字体 xff0c 否则点击OK无效 xff08 虽然在我电脑上确实是这样但是不知道为什么 xff0c 如果有知道的同学希望能

  • 关于递归问题的一点见解

    背景 前不久参加牛客网的有书共读活动意外的获得了一本 具体数学 xff0c 对此感谢牛客 其次领书是要条件的 xff0c 条件就是写读书笔记 搞ACM的都知道具体数学是本什么样的神书 xff08 也可能是我太弱了 xff09 xff0c 不

热门标签