遞歸聯合可以優化嗎？

Question

在實現工會發現，我通常會用這樣的路徑壓縮寫find功能：

def find(x): 
    if x != par[x]: 
     par[x] = find(par[x]) 
    return par[x] 

這是很容易記住，可以說是方便閱讀。這也是有多少書籍和網站描述算法。

但是，天真編譯，這將使用堆棧內存線性在輸入大小。在許多默認會導致堆棧溢出的語言和系統中。

我知道寫find唯一的非遞歸的方法是這樣的：

def find(x): 
    p = par[x] 
    while p != par[p]: 
     p = par[p] 
    while x != p: 
     x, par[x] = par[x], p 
    return p 

這似乎不大可能，許多編譯器會發現。 （也許哈斯克爾會呢？）

我的問題是在什麼情況下使用前版本find是安全的？如果沒有廣泛使用的語言可以刪除遞歸，我們不應該告訴人們使用迭代版本嗎？並且可能會有更簡單的迭代實現？

Answer 1

這裏似乎有兩個單獨的問題。

首先 - 可以優化編譯器注意到這一點，並重寫它？如果不測試所有編譯器和所有版本，就很難回答這個問題。我想這一點，使用以下代碼的gcc 4.8.4：

size_t find(size_t uf[], size_t index) { 
    if (index != uf[index]) { 
    uf[index] = find(uf, uf[index]); 
    } 
    return uf[index]; 
} 

void link(size_t uf[], size_t i, size_t j) { 
    uf[find(uf, i)] = uf[find(uf, j)]; 
} 

這不落實工會按排名優化，但不支持路徑壓縮。我編譯這個使用優化級別-O3和組件如下所示：

find: 
.LFB23: 
    .cfi_startproc 
    pushq %r14 
    .cfi_def_cfa_offset 16 
    .cfi_offset 14, -16 
    pushq %r13 
    .cfi_def_cfa_offset 24 
    .cfi_offset 13, -24 
    pushq %r12 
    .cfi_def_cfa_offset 32 
    .cfi_offset 12, -32 
    pushq %rbp 
    .cfi_def_cfa_offset 40 
    .cfi_offset 6, -40 
    pushq %rbx 
    .cfi_def_cfa_offset 48 
    .cfi_offset 3, -48 
    leaq (%rdi,%rsi,8), %rbx 
    movq (%rbx), %rax 
    cmpq %rsi, %rax 
    je .L2 
    leaq (%rdi,%rax,8), %rbp 
    movq 0(%rbp), %rdx 
    cmpq %rdx, %rax 
    je .L3 
    leaq (%rdi,%rdx,8), %r12 
    movq %rdx, %rax 
    movq (%r12), %rcx 
    cmpq %rcx, %rdx 
    je .L4 
    leaq (%rdi,%rcx,8), %r13 
    movq %rcx, %rax 
    movq 0(%r13), %rdx 
    cmpq %rdx, %rcx 
    je .L5 
    leaq (%rdi,%rdx,8), %r14 
    movq %rdx, %rax 
    movq (%r14), %rsi 
    cmpq %rsi, %rdx 
    je .L6 
    call find   // <--- Recursion! 
    movq %rax, (%r14) 
.L6: 
    movq %rax, 0(%r13) 
.L5: 
    movq %rax, (%r12) 
.L4: 
    movq %rax, 0(%rbp) 
.L3: 
    movq %rax, (%rbx) 
.L2: 
    popq %rbx 
    .cfi_def_cfa_offset 40 
    popq %rbp 
    .cfi_def_cfa_offset 32 
    popq %r12 
    .cfi_def_cfa_offset 24 
    popq %r13 
    .cfi_def_cfa_offset 16 
    popq %r14 
    .cfi_def_cfa_offset 8 
    ret 
    .cfi_endproc 

鑑於中東遞歸調用的存在，它看起來並不像該尾調用被淘汰出局。公平地說，那是因爲你所描述的轉變是非常平凡的，所以我沒有驚訝它沒有找到它。這並不意味着沒有優化編譯器可以找到它，但那一個主要的不會。

你的第二個問題就是爲什麼我們用這種方式來呈現算法。作爲教授算法和編程的人，我認爲使用盡可能簡單的演示來討論算法是非常有價值的，即使這意味着要抽象出一些特定的實現細節。這裏，算法背後的關鍵思想是更新在代表途中遇到的所有節點的父指針。遞歸恰巧是描述這個想法的一種非常乾淨的方式，儘管它在天真的時候可能會導致堆棧溢出。但是，通過以這種特定方式表示僞代碼，描述和討論它並且證明它將按照廣告方式工作更容易。我們可以用另一種方式來描述它，以避免堆棧溢出，但在理論國家，我們通常不會擔心這樣的細節和更新的演示文稿，而更直接地轉化爲實踐，會使得難以看到關鍵想法。

在研究更高級的算法和數據結構的僞代碼時，通常會忽略關鍵重要的實現細節，並且指出某些任務可能在特定的時間範圍內執行。當討論構建在更復雜的算法和數據結構之上的算法或數據結構時，通常不可能爲所有事情寫出僞代碼，因爲在覆蓋層的細節層之上有層之上的層。從理論的角度來看，這很好 - 如果讀者想要實施它，他們可以填補空白。另一方面，如果讀者更關心論文中的關鍵技術和理論（在學術環境中常見），他們不會陷入實施細節。