算法08-递归调用转为循环的通用方法

前导：问题引入

在Python中，递归调用过多会导致“递归深度过深”的错误，通常是因为递归没有正确终止条件或者递归层次太深。
这种错误通常会导致程序抛出 RecursionError 异常。

Python默认的递归深度限制大约是1000层（可以通过sys.getrecursionlimit()查看）。

修正方式是：

import sys
sys.setrecursionlimit(3000)  # 增加递归深度限制

另外就是将递归化为循环。

---

一、递归转循环的通用方法

将递归调用转为循环的普通方法，通常需要使用 栈（Stack） 来模拟递归的调用过程。递归的本质是函数调用栈，而我们可以通过显式地使用栈数据结构来实现相同的逻辑。以下是详细步骤和一个通用的转换方法：

1. 理解递归的执行过程

递归函数的核心是：

• 选择：在当前步骤中做出选择。
• 递归：基于当前选择，进入下一层递归。
• 回溯：撤销当前选择，回到上一步。

2. 使用栈模拟递归

• 栈中存储的是每一步的状态（如当前选择、路径等）。
• 每次从栈中弹出一个状态，处理当前步骤，然后将新状态压入栈中。

3. 通用步骤

1. 初始化一个栈，将初始状态压入栈中。
2. 进入循环，直到栈为空：
   • 弹出栈顶状态。
   • 处理当前状态（如记录结果、更新路径等）。
   • 根据当前状态生成新的状态，并压入栈中。
3. 循环结束后，返回结果。

---

二、递归转循环的核心思想

1. 栈的设计：

   • 栈中存储的是每一步的状态，通常是一个元组或对象，包含当前的选择和路径。
   • 例如，在子集问题中，状态可以是 (start, path)，其中 start 是当前选择的起始位置，path 是当前路径。

2. 循环过程：

   • 弹出栈顶状态，处理当前步骤。
   • 根据当前状态生成新的状态，并压入栈中。
   • 通过循环不断处理栈中的状态，直到栈为空。

3. 回溯的实现：

   • 在生成新状态时，需要确保能够撤销当前选择，以便尝试其他选项。
   • 例如，在子集问题中，选择当前元素后，需要将其从路径中移除，以便尝试其他元素。

---

三、示例：子集问