遞歸遍歷

遞歸的另一個重要應用是遞歸遍歷。

想象一下，我們有一家公司。人員結構可以表示為一個對象:

let?company?=?{
??sales:?[{
????name:?'John',
????salary:?1000
??},?{
????name:?'Alice',
????salary:?1600
??}],

??development:?{
????sites:?[{
??????name:?'Peter',
??????salary:?2000
????},?{
??????name:?'Alex',
??????salary:?1800
????}],

????internals:?[{
??????name:?'Jack',
??????salary:?1300
????}]
??}
};

換句話說，一個公司有部門。

一個部門可能有一系列的員工。例如，銷售部有兩名員工:John和Alice。

或者一個部門可以分為子部門，比如開發(fā)部門有兩個分支:站點和內部。他們每個人都有自己的員工。

當一個子部門增長時，它也有可能劃分為子部門(或團隊)。

例如，未來的站點部門可能會被分為siteA和siteB兩個團隊。而且，它們可能會分裂得更多。這不在圖上，只是在腦海里。

現(xiàn)在假設我們想要一個函數(shù)來得到所有工資的總和。我們怎么做呢?

迭代的方法并不容易，因為結構并不簡單。第一個想法可能是在公司上創(chuàng)建一個for循環(huán)，在第一級部門上嵌套子循環(huán)。但是，我們需要更多嵌套的子循環(huán)來迭代第二級部門(如站點)的員工……然后在那些第三級部門中再出現(xiàn)一個子循環(huán)，將來會出現(xiàn)嗎?如果我們在代碼中放置3-4個嵌套的子循環(huán)來遍歷單個對象，它就會變得相當丑陋。

讓我們嘗試遞歸。

正如我們所看到的，當函數(shù)得到一個要求和的部門時，有兩種可能的情況:

它要么是一個擁有一組人員的“簡單”部門——然后我們可以在一個簡單的循環(huán)中對工資進行合計。

或者它是一個有N個子部門的對象——然后我們可以進行N次遞歸調用，以得到每個子部門的和并組合結果。

第一種情況是遞歸的基礎，這種簡單的情況，當我們得到一個數(shù)組。

當我們得到一個對象的第二種情況是遞歸步驟。一個復雜的任務被分割成小部門的子任務。他們可能會再次分裂，但遲早會在(1)處結束分裂。

從代碼中讀取算法可能更容易:

let?company?=?{?//?the?same?object,?compressed?for?brevity
??sales:?[{name:?'John',?salary:?1000},?{name:?'Alice',?salary:?1600?}],
??development:?{
????sites:?[{name:?'Peter',?salary:?2000},?{name:?'Alex',?salary:?1800?}],
????internals:?[{name:?'Jack',?salary:?1300}]
??}
};

//?The?function?to?do?the?job
function?sumSalaries(department)?{
??if?(Array.isArray(department))?{?//?case?(1)
????return?department.reduce((prev,?current)?=>?prev?+?current.salary,?0);?//?sum?the?array
??}?else?{?//?case?(2)
????let?sum?=?0;
????for?(let?subdep?of?Object.values(department))?{
??????sum?+=?sumSalaries(subdep);?//?recursively?call?for?subdepartments,?sum?the?results
????}
????return?sum;
??}
}

alert(sumSalaries(company));?//?7700

代碼很短，容易理解(希望如此?)這就是遞歸的力量。它也適用于任何層次的子部門嵌套。

下面是調用的圖表:

我們很容易看到這個原則:對于一個對象{…}子調用，而數(shù)組是遞歸樹的“葉”，它們給出直接的結果。

注意，代碼使用了我們之前介紹過的智能特性:

加勒比海盜的方法。reduce在Array方法中解釋了獲取數(shù)組和的方法。
循環(huán)(val of object .values(obj))以遍歷對象值:object。values返回它們的數(shù)組。

接著講遞歸遍歷

遞歸遍歷