什麼是遞歸樹？

Question

在閱讀更多關於合併排序時，我遇到了遞歸樹。什麼是遞歸樹？他們幫助解決遞歸問題嗎？我們通過繪製遞歸樹實現了什麼？谷歌沒有幫助我。

Answer 1

遞歸樹可以證明遞歸在解決問題中有多大用處，還可以幫助揭示更壞/最好的情況。例如，如果你的二分查找算法的遞歸樹總是選擇最正確的路徑，那麼你可能會遇到更壞的情況（因爲你的程序不是分支的，爲什麼還要用樹來表示它？）。通過一組輸入繪製算法的遞歸操作樹，也可以激發您思考如何將遞歸程序更改爲迭代，這可能會或可能不會節省大量內存/時間。

或者它可以使你的遞歸程序看起來非常好，因爲你可能會發現它填滿了所有的葉子，然後再移動到下一層，並設置你在樹上快速操作。一個很好的例子就是紅黑二叉搜索樹，但以遞歸方式繪製出來要比合並排序困難得多。