迭代版本的递归算法来制作二叉树

Question

鉴于此算法,我想知道是否存在迭代版本.另外,我想知道迭代版本是否更快.

这种伪蟒...

该算法返回对树的根的引用

make_tree(array a)
  if len(a) == 0
        return None;

  node = pick a random point from the array
  calculate distances of the point against the others
  calculate median of such distances
  node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances)
  node.right = make_tree(subset, such the distance is greater or equal to the median)
  return node

Answer 1

只有一个递归调用的递归函数通常可以转换为尾递归函数而不需要太多努力,然后将它转换为迭代函数是微不足道的.这里的规范示例是阶乘:

# naïve recursion
def fac(n):
    if n <= 1:
        return 1
    else:
        return n * fac(n - 1)

# tail-recursive with accumulator
def fac(n):
    def fac_helper(m, k):
        if m <= 1:
            return k
        else:
            return fac_helper(m - 1, m * k)
    return fac_helper(n, 1)

# iterative with accumulator
def fac(n):
    k = 1
    while n > 1:
        n, k = n - 1, n * k
    return k

但是,这里的情况涉及两个递归调用,除非您重新编写算法,否则需要保持堆栈.管理自己的堆栈可能比使用Python的函数调用堆栈快一些,但增加的速度和深度可能不值得复杂.这里的规范示例是Fibonacci序列:

# naïve recursion
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

# tail-recursive with accumulator and stack
def fib(n):
    def fib_helper(m, k, stack):
        if m <= 1:
            if stack:
                m = stack.pop()
                return fib_helper(m, k + 1, stack)
            else:
                return k + 1
        else:
            stack.append(m - 2)
            return fib_helper(m - 1, k, stack)
    return fib_helper(n, 0, [])

# iterative with accumulator and stack
def fib(n):
    k, stack = 0, []
    while 1:
        if n <= 1:
            k = k + 1
            if stack:
                n = stack.pop()
            else:
                break
        else:
            stack.append(n - 2)
            n = n - 1
    return k

现在,你的情况比这更难:一个简单的累加器将难以表达一个部分构建的树,其中指针指向需要生成子树的位置.你需要一个拉链 - 不容易用像Python这样的非功能性语言来实现.

Answer 2

制作迭代版本只是使用自己的堆栈而不是普通的语言调用堆栈.我怀疑迭代版本会更快,因为普通的调用堆栈是为此目的而优化的.