遞歸算法的迭代版本，以二叉樹

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; 
} 

的