遞歸樹

遞歸樹是疊代過程的一種圖像表述。遞歸樹往往被用於求解遞歸方程， 它的求解表示比一般的疊代會更加的簡潔與清晰。

基本介紹

• 中文名：遞歸樹
• 外文名：recursive tree
• 領域：算法設計與分析
• 定義：疊代過程的一種圖像表述

概念

遞歸樹是疊代計算的模型。

遞歸樹的生成過程與疊代過程一致。

遞歸樹上所有項恰好是疊代之後產生和式中的項。

對遞歸樹上的項求和就是疊代後方程的解。

生成規則

1、初始：遞歸樹只有根結點，其值為W(n)

2、不斷繼續下述過程：

將函式項葉結點的疊代式W(m)表示成二層子樹

用該子樹替換該頁結點

3、繼續遞歸樹的生成，直至樹中無函式項（只有初值）為止。

例子

遞歸樹1

由遞歸式T(n) = 3T(n / 4) + cn^2所繪製出的右側的遞歸樹模型：

遞歸樹2