如何将递归问题高效转为迭代实现？以merge-sort为例

所有递归都可转迭代的结论是成立的，本质是因为递归的底层实现就是编程语言帮你维护了一个调用栈，存储每一层递归的参数、中间结果和执行位置，你只要手动模拟这个栈的行为，就能实现和递归逻辑完全一致的迭代版本，时间复杂度和原递归完全相同，不需要走暴力搜索。

通用转换方法 #

• 手动模拟调用栈法：这是适配所有递归场景的通用方案，没有额外的时间损耗。你需要为每个栈元素存储三类信息：当前递归层的所有入参、当前层的执行状态标记（比如是否已经完成子递归的调用，下一步需要执行什么逻辑）、已经得到的子递归返回值。处理时每次取出栈顶元素：如果还没执行子调用，就先把当前元素的状态标记为「待处理子结果」后放回栈，再按递归调用的逆序把所有子调用的参数压入栈（比如递归先调用左子树再调用右子树，就先压右子树的参数，再压左子树的参数，保证栈顶是先执行的子调用）；如果子调用的结果已经全部返回，就计算当前层的结果，弹出当前栈元素，把结果传给上一层。
• 尾递归直接转循环：如果原递归是尾递归（递归调用是函数的最后一步执行逻辑，不需要保留当前层的任何中间结果等待子调用返回），可以直接改成循环实现，不需要手动维护栈，只需要每次迭代更新入参的值即可，空间复杂度可以优化到O(1)，比如阶乘、斐波那契的尾递归版本都可以用这种方式快速转换。
• 自底向上递推法：如果递归问题存在重叠子问题，拆解逻辑是自顶向下把大问题拆成更小的同类型子问题，你可以反过来从最小的可直接求解的子问题出发，逐步向上合并结果得到原问题的解，典型场景就是动态规划、归并排序等，这种方式不需要维护栈结构，运行效率通常更高。

迭代版归并排序实现（时间复杂度O(nlogn)） #

递归版归并排序是自顶向下拆分数组，分别排序左右子数组后合并，迭代版可以用自底向上的思路实现，和递归版的时间复杂度、空间复杂度完全一致：

1. 初始把数组中每个长度为1的子数组视为已经有序的单元
2. 每次将相邻的两个有序子数组合并，得到长度翻倍的有序子数组
3. 不断重复合并操作，直到所有子数组合并为完整的有序数组

代码示例 #

def merge_sort_iterative(arr):
    n = len(arr)
    # 待合并的子数组初始长度为1
    sub_length = 1
    while sub_length < n:
        # 遍历所有相邻的子数组对
        left = 0
        while left < n:
            # 计算左右两个子数组的边界
            mid = min(left + sub_length - 1, n - 1)
            right = min(left + 2 * sub_length - 1, n - 1)
            # 合并两个有序子数组
            merge(arr, left, mid, right)
            left += 2 * sub_length
        # 合并完成后子数组长度翻倍
        sub_length *= 2
    return arr

def merge(arr, left, mid, right):
    temp = []
    i, j = left, mid + 1
    # 双指针合并两个有序数组
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    # 拼接剩余元素
    temp.extend(arr[i: mid + 1])
    temp.extend(arr[j: right + 1])
    # 将合并结果写回原数组
    arr[left: right + 1] = temp

整个算法需要执行logn轮合并操作，每轮合并的总元素个数为n，因此时间复杂度稳定为O(nlogn)，和递归版没有差异。

内容的提问来源于stack exchange，提问作者Noman Tanveer