递归转迭代 • quietin

继续算法学习

有很多平常所见的算法，递归的算法都要更加的简单直观，比如二叉树的遍历和求深度，以及快排

但是递归的问题是在连续的函数调用，得到最后的结果前可能会导致栈溢出，这里的栈，指线程栈，这个栈在linux上的大小一般是8M。输入limit可以在输出中看到栈大小等数据(用ulimit -s也可以)，我机器上的结果是这样

这个栈大小下，只要不是递归太深一般也没有问题，但是掌握迭代的写法还是非常有必要的，毕竟程序就是数据结构+算法嘛，用迭代的方式写还是更可靠些，另外的好处就是可以应付面试

递归转迭代的方法，我自己归纳了一下，大概两种

第一种是使用tail call(尾递归)和continuation-passing(即大名鼎鼎的CPS，中文叫后继传递格式）。具体就是先要把function改成尾递归的形式，然后使用CPS，将部分结果存入一个累加器参数中，return到下一次调用。变成尾递归形式后就比较好分析了，然后由递归改成带while的迭代形式举个例子

# original ver
def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)

# tail call ver
def factorial1a(n, acc=1):
     if n < 2:
         return 1 * acc
     return factorial1a(n - 1, acc * n)

# iterative ver
def factorial(n, acc=1):
    while n > 1:
        (n, acc) = (n - 1, acc * n)
    return acc

具体变换过程在这里，原文太长了。。。有兴趣的可仔细研读

另外一种就是使用stack了，比如快排的迭代写法。快排不用栈的迭代写法，谷歌娘也没有找到，应该是必须得用。用栈迭代写法的原理是通过大区间的分解产生小区间，并不断入栈，直到栈为空为止

# recursive ver
def qsort(arr):
     if len(arr) <= 1:
          return arr
     else:
          return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])

# iterative ver
def quick_sort_iterative(r):
    left, right = 0, len(r) - 1
    tmp_stack = [(left, right)]
    while tmp_stack:
        left, right = tmp_stack.pop()
        pos = partition(r, left, right)
        if pos - 1 > left:
            tmp_stack.append((left, pos - 1))
        if pos + 1 < right:
            tmp_stack.append((pos + 1, right))

def partition(r_list, left, right):
    piv = r_list[left]
    i = left + 1
    j = right
    while True:
        while i <= j and r_list[i] <= piv:
            i += 1
        while i <= j and r_list[j] >= piv:
            j -= 1
        if j <= i:
            break

        r_list[i], r_list[j] = r_list[j], r_list[i]

    r_list[left], r_list[j] = r_list[j], r_list[left]
    return j

使用上面的迭代写法，使用randint生成包含100000个0~100000间数字的list，stack的大小基本不超过30，且元素仅是包含位置的元组

原文发布于 SegmentFault。