关于递归法

手机软件开发 · 2024-9-17 23:26:13

一个过程或函数在其界说或分析中又直接或间接调用自身的一种方法，它通常把一个大型复杂的题目转化为一个与原题目相似的规模较小的题目来求解，递归计谋只需少量的步伐就可形貌出解题过程所须要的多次重复盘算，大大地镌汰了步伐的代码量。递归的本领在于用有限的语句来界说对象的无穷聚集。一般来说，递归须要有边界条件、递归进步段和递归返回段。当边界条件不满意时，递归进步；当边界条件满意时，递归返回。
递归算法一般用于办理三类题目：
（1）数据的界说是按递归界说的。（Fibonacci函数）
（2）题目解法按递归算法实现。（回溯）
（3）数据的结构情势是按递归界说的。（树的遍历，图的搜索）

递归的实验过程可分为分解和求值两部门。起首是渐渐把“大题目”分解成情势类似但规模很小的“小题目”，直至分解到递归出口。一旦遇到递归出口，分解过程竣事，开始求值过程，以是分解过程是“量变”过程，即原来的“大题目”在逐步变小，但尚未办理。遇到递归出口后，便发生了“质变”，即原递归题目转换成直接可以求值的简朴题目。递归只须要少量的步调就可形貌解题过程中所须要的多次重复盘算，极大地镌汰了代码量。该算法计划的关键在于，找出递归方程和边界条件（递归出口）。递归关系就是使题目向边界条件转化的过程，以是递归关系必须能使题目越来越简朴，规模越小。没有设定边界的递归是死循环。
递归算法计划通常须要按照以下3个步调：
（1）分析题目，得出递归关系；
（2）设置边界条件，控制递归；
（3）计划函数，确定参数。

递归算法具有以下三个基本规则：
（1）基本情况：至少有一种无需递归即可得到办理的情况，也即前面说的边界条件。
（2）盼望：恣意递归调用必须向基本情况迈进，即前面所说的使得题目规模变小。
（3）精确性假设：总是假设递归调用是有用的。
递归调用的有用性是可以用数学归纳法证实的，以是当我们在计划递归函数时，不必想法跟踪可能很长的递归调用途径（比如Hanoi Tower题目）。这种任务可能很贫苦，易于使计划和验证变得更加困难。以是我们一旦决定使用递归算法，则必须假设递归调用是有用的。

与递归相对应的递推算法是一种用多少步可重复的简朴运算（规律）来形貌复杂题目标方法。
递推算法以初始（出发点）值为底子，用类似的运算规律，逐次重复运算，直至运算竣事。这种从“出发点”重复类似的方法直至到达肯定“边界”，如同单向运动，用循环可以实现。递推的本质是按规律逐次推出（盘算）先一步的结果。
在算法计划时，能用递推实现的算法一般都可以用递归来实现。能用递归实现的算法不愿定可以或许通过递推实现。就算法的服从而言，递推优于递归

关于递归法

所属分类: 问答交流

新帖推荐: 30日

推荐作品