| 标题 | 从递归算法看数学在计算机程序设计方面的应用与研究 |
| 范文 | 李青柏 摘 要：数学在计算机程序设计中具有重要地位，通过数学思维、数学计算方法、数学模型的建立等将实际问题不断抽象化，并设计相应的计算机程序获得问题的解，是一个简洁、高效的设计过程，程序员可以将实际问题通过各种科学计算转换为程序，在这一过程中，数学算法的合理应用具有重要意义。文章以递归算法在计算机程序设计中的运用作为基础，探讨数学计算在计算机程序设计中的重要作用。 关键词：递归算法；数学；计算机程序设计 递归是函数、过程、子程序运行过程中对自身行为的一种直接或间接调用，是一个重要的计算机科学概念，一般将采用了递归思想的算法称为递归算法。递归方法是一种有效的程序设计方法，通过递归算法编写程序能够提高程序的简洁性与清晰度。在程序设计中运用递归能够定义句法，而在数据结构中则能够用递归解决表或树形结构排列问题。运用递归算法设计计算机程序，也是运用数据思想构造算法与设计程序的一个重要体现[1]。 1 递归算法在计算机程序设计中的运用设计 1.1 递算法设计的一般步骤 递归算法设计时，主要通过3个步骤完成：（1）分析问题，理解题意，设计递归关系表达式。（2）设计递归终止表达式，有效控制递归循环，使递归结束时能够获得原问题的解。（3）明确形式参数，设计递归函数[2]。 1.2 设计递归关系式 这一步是将一个问题转换为若干个子问题进行求解，子问题与原问题需要有相同解法，一些问题可以通过一个关系式求解，如FIBONACCI数列，可以运用f（n）=f（n-1）+f（n+2）迭代处理。一些问题则需要运用循环求解，如将一个十进制数n转化成二进制数进行输出，从而执行下一个循环，第一步，先输出为n的2的余数即n%2；第二步，将n右移一位数或直接求解n/2，当结束为0时表示输出后即可结束递归，当结果不为0时，需要继续执行上一步骤。递归调用语言d2b（n/2）必须放在语言count< 1.3 设计递归终止条件 最后一级递归调用时，必须确保无法再次进行递归，有明确的递归函数返回值，避免无穷递归。递归调用普遍要受条件控制，调用过程中，调用函数对应的参数修改有一定规律，每一次递归均要使递归能够趋于结束，能够进一步满足终止条件，满足返回值，进而结束递归，之后再从原路径逐层进行返回，从而获得原问题的解。问题不同时，递归终止条件也不同，可能对应一个或多个终止条件。如，自然数阶乘问题的求解，仅对应一条调用程序，递归终止条件仅有一个。一般情况下，阶乘都属于自然数范围，任意自然数阶乘可以表述为：n！=1×2×3×…n，递归表述为：0！=1，1！=1，…n！=n×（n-1）！。递归求解n！时，就需要满足两个关键问题，即递归终止条件，确保0！与1！能够直接求解；递归表达式，求解n！时可以直接转换为求解（n-1）！，n！的递归函数就可以采用如下语句设计： 采用精度为24位的long long作为函数返回值，仅能够计算到20！，阶乘范围超过20时，会超出long long数据的显示范围，就需要采用double作为函数返回类型。 当递归过程或函数不止对应一条自身调用程序时，就会出现多个递归终止条件。如爬楼梯问题的分析，通过递归算法解决时，递推至一定程度后，会面临剩余楼梯数量不同，解法不同的问题，那么就会出现多个递归终止条件。 1.4 确定参数，设计递归函数 递归函数需要多次自我调用，子问题规模足够小时，需要直接给出解，而不能再作递归调用，因此每次递归均是有条件的，无条件递归会造成死循环，无法正常结束。递归过程或函数对应的参数在递归过程中是按照一定的规律变化的，函数值增减方向能够和递归终止条件匹配，确保递归调用在可控范圍内[3]。因此，递归函数一般设计形式主要可以通过以下语句描述： T func（mode）//T可以是void，即递归函数不一定必须有返回值，mode是参数的一般模式： 因此，递归问题求解步骤一般为：理解原问题的意思，获得待求问题解，对应函数为f（n）；寻求另一个函数g（），确保f（n）=g（f（n-1）），原问题解能够通过一些小问题解表示，寻求递推关系式，（n-1）一般为n/2，使问题规模能够逐渐缩小；确保f（0）与f（1）为已知值，从而通过这两个已知的值与函数g（）求得f（n）的解。 1.5 递归算法执行过程 执行递归算法的过程是由回溯与递推两个步骤完成的，回溯是指逐层递归调用，递推即按原路径层层递归返回两个步骤，回溯时需要保存断点地址、形式参数与局部变量，控制整个求解过程是直接趋向于递归调用入口的过程。递推是在本次递归调用结束后，逐层向上一层递归调用返回，同时要保存本次调用函数结题，使后续求解能够继续按照原局部变量与形式参数进行求解，并通过调用时出现的断点地址控制递归流程逐渐向调用函数下一行代码处转回，以便于执行下一个循环。从以上过程可以看出，递归算法执行过程就意味着需要不断进行自调用，逐步递归到终止条件出现后，即可结束自调用，达到条件后，再通过最后调用过程逐步自最先返回的次序开始进行逐层返回求解，在返回到最外层的调用语句时，表明这一执行过程完结。 1.6 递归算法的问题 递归算法在求解时有一个较严重的问题，以FIBONACCI数列为例如果需要计算40！时，基本计算涉及39次加法，即使在运行速度相对较快的计算机上也需要较长时间的运行，时间花费过大，其根本问题就在于递归的多余计算较多，计算f（n）时，就需要计算f（n-1），依次类推，后续计算还会涉及f（n-2），f（n-3）等的计算，需要多次对上一次计算结果进行递归调用，每一次递归均对应更多的计算过程，计算效率较低，因此，需要确保递归过程中不需要通过单独的递归调用对类似问题进行处理，以避免问题复杂化。 2 计算机程序设计中的数学应用分析 数学是目前各门科学的重要基础，计算机科学从一开始仅是一个数学分支，时代的发展使计算机与数学之间的关系不断密切化，计算机实际上已经成为一个重要的计算工具，要解决实际问题时，可以运用各种科学计算设计一个计算机程序，直接将实际问题抽象转换成计算机程序，这一转换过程就是实际问题的不断抽象化过程，运用合理的数学算法设计一个完善、简洁、清晰的数学模型，才能够实现实际问题到计算机程序的转换，这就要求程序员的数学科学基础更为完备。算法是软件程序最为重要的思想，算法又是以数学思维为基础的，程序仅是外在，算法才是其灵魂，算法以数学为基础，若不具备丰富的数学思维，就无法弄懂算法。如，四色问题的求解就涉及几何、离散数学、小波分析、有限单元数值计算法、仿生计算等多个数学分支；运用莱文宾—杜宾递推算法的大规模矩阵运算还能够在VC++环境下设计一个滤波器模拟软件；数字信号的处理也涉及三角函数、傅里叶变换、微积分、数值逼近及高次方程求解等多种数学基础知识。因此，数学知识在计算机程序设计中具有重要地位，要解决一些程序设计当中的问题，需要运用各种数学思想及计算方法，使程序员能够将实际问题有效转换为计算机程序，通过一个有效的抽象过程，使实际问题能够转换为数学模型，进而完成程序设计。 3 结语 从递归算法在计算机程序设计的应用中可以发现，抽象数学问题的解决，首先需要完成数学模型设计的问题，运用相应的算法设计一个完善的数学模型，建立一个有效的逻辑结构后，再进行程序设计。合理运用数学解题方法，能够使计算机编程更为方便。 [参考文献] [1]周法国.基于递归的程序设计浅析[J].天津科技，2017（6）：103-105. [2]迟呈英，王玄同，王子涵，等.数学解题方法与程序设计关系的研究[J].软件工程，2016（2）：16-18. [3]张耀民.递归算法在程序设计中的应用与分析[J].电子测试，2013（7S）：1-2. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。