自我測驗
本篇文章的測驗用例及除錯方法見前言
說明
遞回是一種解決問題的方法,他從解決問題的各個小部分開始,直到解決最初的大問題.遞回通常涉及函式呼叫自身.
const test = (i) => {
console.log(i)
test(++i);
}
這是一種明顯的遞回,自己呼叫自己
function test2(i){
console.log("test2: " + i++)
test(i)
}
function test(i){
console.log("test: " + i++)
test2(i)
}
這個也是一種遞回,通過兩個方法之間的相互呼叫,然后實作遞回.但是這種代碼我們一般是不會直接拿去運行的.為什么呢???
相信你也看出來了,上面的遞回寫法有問題,我呼叫我自己,然后自己呼叫自己,然后自己又呼叫了自己......,形成了一個倍訓,所以遞回的最重要的一個點出現了 基線條件(跳出回圈的條件)
呼叫堆疊(這個對后面分析遞回很重要)
每當一個函式被一個演算法呼叫時,該函式會進入呼叫堆疊的頂部.當使用遞回的時候,每個函式呼叫都會堆疊在呼叫堆疊的頂部,這是因為每個呼叫都可能依賴前一個呼叫的結果
尾部呼叫優化(ES2015新知識點)
案例
let i = 0;
function recursiveFn(){
i++;
recursiveFn();
}
try{
recursiveFn();
}catch(ex){
console.log(ex)
}
如果函式內的最后一個操作是呼叫函式(如案例),會通過"跳轉指令"(jump)而不是"子程式呼叫"(subroutine call)來控制.也就是說,在ES2015中,這里的代碼可以一直執行下去.因此,具有停止遞回的基線條件非常重要尾呼叫優化更多資訊
練習
階乘
說明:
5的階乘: 5 * 4 * 3 * 2 * 1
9的階乘: 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
代碼
function recursionFactorial(num: number): number {
//找到結束條件
if (num === 1) {
return 1;
}
return num * recursionFactorial(num - 1);
}
還是一定要找到 基線條件,這個是遞回的必要條件,不然你的程式會死回圈,然后卡死
圖解
是否還喜歡這種圖解,如果喜歡,可以進入下一篇章第十章 樹,帶你走進樹的遍歷
斐波那契數列
說明
0 1 1 2 3 5 8 13 21 34 ....
第1個數: 0
第2個數: 1
第3個數 = 第2個數 + 第1個數
第4個數 = 第2個數 + 第3個數
第5個數 = 第4個數 + 第3個數
........
圖解
代碼
/*求n個斐波那契數的和*/
function newRecursionSequence(n: number): number {
if (n === 0) return 0;
if (n <= 2) return 1
return newRecursionSequence(n - 1) + newRecursionSequence(n - 2);
}
優化版代碼
function newNewRecursionSequence(n: number) {
let memo: Array<number> = [0, 1];
let fbnc = (n: number): number => {
if (memo[n] != null) return memo[n];
//新算出的值保存在memo陣列里
return memo[n] = fbnc(n - 1) + fbnc(n - 2);
}
return fbnc(n);
}
優化版對比第一版好在對資料進行了快取,這樣就不用反復的計算資料(圖解中可以看到我們反復計算了n為 3 ,2等時的值)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/226407.html
標籤：其他
下一篇：第十章 樹