递归算法的迭代版本，以二叉树

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的函数调用堆栈快一点，但增加的速度和深度可能不值得这样复杂。这里典型的例子是斐波那契序列：

# 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 

现在，你的情况比这更严厉了很多：一个简单的储液器有困难表达部分建造树的指针，其中一个子树必须产生。你会想要一个zipper - 不容易实现在一个非真正功能的语言，如Python。

Answer 2

制作一个迭代版本的根一提的是简单地使用你自己的堆栈，而不是的问题正常的语言调用栈。我怀疑迭代版本会更快，因为正常的调用堆栈已针对此目的进行了优化。

Answer 3

是的，它可以使任何递归算法迭代。隐式地，当您创建递归算法时，每个调用都会将先前的调用放入堆栈。你想要做的是使隐式调用堆栈变成一个明确的调用堆栈。迭代版本不一定会更快，但您不必担心堆栈溢出。 （我会得到一个徽章在我的答案使用本网站的名字吗？

Answer 4

虽然在一般意义上，递归算法直接转换成一个迭代将需要一个明确的堆栈真实的，有特定的子这些渲染可能不具有相同的性能保证（遍历功能列表与递归解构），但它们确实经常存在。

Answer 5

这是一个以迭代形式直接呈现的算法集（不需要堆栈）。你得到的数据是随机的，因此树可以是任意的二进制树。对于这种情况，你可以使用一个线程二叉树，它可以遍历并内置W/O递归和没有堆栈，节点具有指示标志如果链接是到另一个节点的链接或者如何到达“下一个节点”

从http://en.wikipedia.org/wiki/Threaded_binary_tree

Answer 6

取决于你如何定义“迭代”，没有通过前面的答案中提到的另一个解决方案。如果“迭代”只是意味着“没有受到堆栈溢出异常”（但“允许使用‘让REC’”），然后在支持尾调用一种语言，你可以使用continuation（而不是“明确写一个版本栈“）。下面的F＃代码说明了这一点。它与你最初的问题类似，因为它从一个数组中构建了一个BST。如果数组随机混洗，则树相对平衡，递归版本不会创建太深的堆栈。但关闭混洗，并且树不平衡，递归版本堆栈溢出而迭代连续版本继续愉快。

#light 
open System 

let printResults = false 
let MAX = 20000 
let shuffleIt = true 

// handy helper function 
let rng = new Random(0) 
let shuffle (arr : array<'a>) = // ' 
    let n = arr.Length 
    for x in 1..n do 
     let i = n-x 
     let j = rng.Next(i+1) 
     let tmp = arr.[i] 
     arr.[i] <- arr.[j] 
     arr.[j] <- tmp 

// Same random array 
let sampleArray = Array.init MAX (fun x -> x) 
if shuffleIt then 
    shuffle sampleArray 

if printResults then 
    printfn "Sample array is %A" sampleArray 

// Tree type 
type Tree = 
    | Node of int * Tree * Tree 
    | Leaf 

// MakeTree1 is recursive 
let rec MakeTree1 (arr : array<int>) lo hi = // [lo,hi) 
    if lo = hi then 
     Leaf 
    else 
     let pivot = arr.[lo] 
     // partition 
     let mutable storeIndex = lo + 1 
     for i in lo + 1 .. hi - 1 do 
      if arr.[i] < pivot then 
       let tmp = arr.[i] 
       arr.[i] <- arr.[storeIndex] 
       arr.[storeIndex] <- tmp 
       storeIndex <- storeIndex + 1 
     Node(pivot, MakeTree1 arr (lo+1) storeIndex, MakeTree1 arr storeIndex hi) 

// MakeTree2 has all tail calls (uses continuations rather than a stack, see 
// http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!171.entry 
// for more explanation) 
let MakeTree2 (arr : array<int>) lo hi = // [lo,hi) 
    let rec MakeTree2Helper (arr : array<int>) lo hi k = 
     if lo = hi then 
      k Leaf 
     else 
      let pivot = arr.[lo] 
      // partition 
      let storeIndex = ref(lo + 1) 
      for i in lo + 1 .. hi - 1 do 
       if arr.[i] < pivot then 
        let tmp = arr.[i] 
        arr.[i] <- arr.[!storeIndex] 
        arr.[!storeIndex] <- tmp 
        storeIndex := !storeIndex + 1 
      MakeTree2Helper arr (lo+1) !storeIndex (fun lacc -> 
       MakeTree2Helper arr !storeIndex hi (fun racc -> 
        k (Node(pivot,lacc,racc)))) 
    MakeTree2Helper arr lo hi (fun x -> x) 

// MakeTree2 never stack overflows 
printfn "calling MakeTree2..." 
let tree2 = MakeTree2 sampleArray 0 MAX 
if printResults then 
    printfn "MakeTree2 yields" 
    printfn "%A" tree2 

// MakeTree1 might stack overflow 
printfn "calling MakeTree1..." 
let tree1 = MakeTree1 sampleArray 0 MAX 
if printResults then 
    printfn "MakeTree1 yields" 
    printfn "%A" tree1 

printfn "Trees are equal: %A" (tree1 = tree2) 

Answer 7

在这里是基于堆栈迭代溶液（爪哇）：

public static Tree builtBSTFromSortedArray(int[] inputArray){ 

    Stack toBeDone=new Stack("sub trees to be created under these nodes"); 

    //initialize start and end 
    int start=0; 
    int end=inputArray.length-1; 

    //keep memoy of the position (in the array) of the previously created node 
    int previous_end=end; 
    int previous_start=start; 

    //Create the result tree 
    Node root=new Node(inputArray[(start+end)/2]); 
    Tree result=new Tree(root); 
    while(root!=null){ 
     System.out.println("Current root="+root.data); 

     //calculate last middle (last node position using the last start and last end) 
     int last_mid=(previous_start+previous_end)/2; 

     //*********** add left node to the previously created node *********** 
     //calculate new start and new end positions 
     //end is the previous index position minus 1 
     end=last_mid-1; 
     //start will not change for left nodes generation 
     start=previous_start; 
     //check if the index exists in the array and add the left node 
     if (end>=start){ 
      root.left=new Node(inputArray[((start+end)/2)]); 
      System.out.println("\tCurrent root.left="+root.left.data); 
     } 
     else 
      root.left=null; 
     //save previous_end value (to be used in right node creation) 
     int previous_end_bck=previous_end; 
     //update previous end 
     previous_end=end; 

     //*********** add right node to the previously created node *********** 
     //get the initial value (inside the current iteration) of previous end 
     end=previous_end_bck; 
     //start is the previous index position plus one 
     start=last_mid+1; 
     //check if the index exists in the array and add the right node 
     if (start<=end){ 
      root.right=new Node(inputArray[((start+end)/2)]); 
      System.out.println("\tCurrent root.right="+root.right.data); 
      //save the created node and its index position (start & end) in the array to toBeDone stack 
      toBeDone.push(root.right); 
      toBeDone.push(new Node(start)); 
      toBeDone.push(new Node(end)); 
     } 

     //*********** update the value of root *********** 
     if (root.left!=null){ 
      root=root.left; 
     } 
     else{ 
      if (toBeDone.top!=null) previous_end=toBeDone.pop().data; 
      if (toBeDone.top!=null) previous_start=toBeDone.pop().data; 
      root=toBeDone.pop();  
     } 
    } 
    return result; 
} 

的