為什么這種遞回方法在這個BST中起作用

我很難理解為什么這段代碼有效

所以我們有一棵樹，我們使用這種方法來計算高度

對我來說，問題是這種方法如何在沒有回圈的情況下計算樹的總高度，或者根據我自己的理解，這只能適用于 1 個節點，但我看不出如何為整個樹作業沒有任何迭代

public int height() {
    if (isEmpty()) {
        return -1;
    }
    else {
        int leftHeight = left.height();
        int rightHeight = right.height();
        return Math.max(leftHeight, rightHeight) 1;
    }
}

uj5u.com熱心網友回復：

但是遞回是一種迭代。

常規回圈重復計算配方，即回圈體，每次重復時（可能）使用回圈變數的新值，直到滿足停止條件。

遞回函式重復計算配方，即函式的主體，在每次呼叫時（可能）使用其引數變數的新值，直到滿足基本測驗條件——然后，回傳前面的呼叫，并繼續執行它們的計算配方(s) - 這是相同的配方，因為它是相同的功能 - 直到所有計算完成。

從概念上講，這是同一件事。

具體來說，您的示例呼叫相同的配方 - 用于計算二叉樹高度的函式 - 分別為每個引數樹的分支，它們本身也是樹，就像引數樹本身一樣。就像回圈的主體對于所有迭代都是相同的。

所以你的函式計算左分支的高度，將它保存在一個臨時變數中；計算右分支的高度，將其保存在另一個臨時變數中；然后結合這兩個結果來產生自己的結果。

因此，它一遍又一遍地重復許多計算步驟。

當特定呼叫遇到葉子時，這被視為基本情況。然后，此呼叫直接回傳其結果，而不呼叫同一配方的任何更多實體。

作為一個例子，（寫作height <tree>意思是<tree>.height()），

height { {{* 1 *} 2 *} 3 {* 4 {{* 5 *} 6 *}} }
=
 set
  a = height {{* 1 *} 2 *}
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = height {* 1 *}
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = /// height {* 1 *}
                   set a3 = height *
                       b3 = height *
                       return max(a3,b3) 1
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = /// height {* 1 *}
                   set a3 = -1
                       b3 = height *
                       return max(a3,b3) 1
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = /// height {* 1 *}
                   set a3 = -1
                       b3 = -1
                       return max(a3,b3) 1
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = /// height {* 1 *}
                       return max(-1,-1) 1
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = 0
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = 0
            b2 = -1
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
            return max(0,-1) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=

繼續，

=
 set
  a = /// height {{* 1 *} 2 *}
            return max(0,-1) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = 1
  b = /// height {* 4 {{* 5 *} 6 *}}
        set a2 = height *
            b2 = height {{* 5 *} 6 *}
            return max(a2,b2) 1
  return max(a,b) 1
=
...... etc.

就像在每次呼叫回圈體之間記住外部變數的值一樣，屬于遞回函式的外部呼叫的變數的外部呼叫的變數會在內部呼叫完成它們的作業時被記住。

這里的關鍵是遞回函式的每次呼叫都是相同計算配方的副本，以及它自己的一組變數，這些變數的使用由該配方規定。

所以配方是一樣的，但每個副本都是獨立的、獨立的、不同的。給定的副本（即呼叫）使用它自己的一組函式配方的變數，并記住它是由哪個副本呼叫的——所以當這個副本完成它的作業時，它的結果將回傳到那里。

當最頂層的副本——第一個被呼叫的——完成時，整個作業就完成了，最終結果作為整體值回傳。

標籤：爪哇递归树迭代二叉搜索树

上一篇：快速遞回：函式與閉包

下一篇：遞回如何在二叉樹中填充子樹值？