递归组合算法，递归算法必须包括的内容

这就是著名的背包问题。

这是一个 n-p 问题，当 n 更大时，不可能找到最多的解。

通常的解决方案是基于贪婪算法。

递归算法由两部分组成：

1.与自身定义的原始问题相似的较小规模的子问题（仅在数据大小上有所不同），使递归过程继续进行，称为一般条件。

2.所描述的问题的最简单情况，即控制递归过程结束的条件，称为基本条件。 （递归导出）。

递归的定义：

如果一个对象部分由自身组成或由自身定义，则称为递归对象，因此递归是由函数过程子过程在操作过程中直接或间接调用自身引起的重入现象。

递归的基本思想：

就是把一个大问题分成几个小的子问题来解决，每个小问题可以分成几个小的子问题。 基本上，所有递归问题都可以用递归公式表示。

最重要的一点是假设子问题已经解决了，现在基于已经解决的子问题解决了当前问题; 也就是说，必须先解决子问题，然后基于子问题解决当前问题，或者可以理解为递归求解具有依赖顺序关系的多个问题。

递归的优缺点：

优点：逻辑清晰、结构清晰、可读性好、简洁、效率高（扩展：DFS深度优先搜索，前、中、后序二叉树遍历）。

缺点：函数调用成本高，空间复杂度高，有堆栈溢出的风险。

递归算法必须包括终止条件和递归部分。

计算机科学中的递归算法是指通过反复将问题分解为同类子问题来解决问题的方法。

递归方法可以用来解决许多计算机科学问题，因此它是计算机科学中的一个重要概念。 绝大多数编程语言都支持函数的自调用，其中函数可以通过调用自身来递归调用。

可以解决的问题数据的定义是递归定义的。 比如斐波那契函数。

问题解决方案是根据递归算法实现的。 比如河内问题。

数据的结构是递归定义的。 如二叉树、广义表等。

1.调用自身的函数是递归函数。

2.递归与普通函数调用一样，是通过堆栈实现的。

3.树和二叉树适用于递归表示。

4.该算法分为基本步骤和归纳步骤。

递归算法是将归纳的思想应用到算法设计中，递归算法充分利用计算机系统的内部功能，自动实现调用过程中相关和必要信息的保存和回复。

1）问题的描述涉及规模。

2）当问题的大小发生变化时，解是完全一样的，原问题的解包括小问题的解。

3）小规模问题可以解决（关机可以用有限的步骤完成） 输入：n 输出：n！

输入：板数 n，列名称 a、b、c

输出：移动方案。

输入：位数 n

输出：斐波那契数列的第 n 位数字的值。

有n个楼梯，一次只能走一两个，所以可以计算出下楼的路有多少条。

算法思路：1N 个数字分为 s1 和 s2

2.分别求解 S1 和 S2 的最大值和最小值。

S1 的最大值为 max1，S1 的最小值为 min1，S2 的最大值为 max2，S2 的最小值为 min23计算 min（min1， min2）， max（max1， max2）。

首先，含义不同：

递归是重复调用函数本身来实现循环。 迭代是函数中实现循环的某个片段，循环中操作涉及的变量也是保存结果的变量，当前保存的结果作为下周期计算的初始值。

在递归循环中，当满足终止条件时，它会逐层返回到末尾。 迭代使用计数器来结束循环。 当然，在许多情况下，它是一种多循环混合物，具体取决于具体需求。

二、结构不同：

递归和迭代都基于控制结构：迭代使用重复结构，而递归使用选择结构。 递归和迭代都涉及重复：迭代显式使用重复结构，而递归通过重复函数调用实现重复。

递归和迭代都涉及终止测试：迭代在循环条件失败时终止，递归在遇到基本情况时终止，使用计数器控制重复和递归的迭代都逐渐到达终点：迭代修改计数器，直到计数器值导致循环条件失败; 递归不断生成初始问题的简化副本，直到达到基本情况。

递归算法通常用于解决三类问题：

1）数据的定义是递归定义的。（斐波那契函数）。

2）根据递归算法实现问题解。

虽然本身没有明显的递归结构，但这种问题比迭代更容易解决，比如河内问题。

3）数据的结构是递归定义的。

例如，二叉树、广义表等，由于结构本身固有的递归性质，它们的操作可以递归地描述。

以上内容参考：百科全书 - 递归。

递归算法是一种使用递归的计算方法，即在函数定义中使用函数本身的计算方法。 递归算法可用于解决许多计算问题，例如搜索、排序和递归。 递归算法通常由基本情况（即不再使用递归的情况）和递归情况组成，其中函数调用自身来解决较小的问题。