JavaScript中遞歸

語言: CN / TW / HK

遞歸 Recursion

To iterate is human, to recurse, divine. 理解迭代,神理解遞歸。

本文會以 JavaScript為主、有部分 Rust 舉例説明。

概述

遞歸就是程序 函數自己 調用自己。遞歸需要有邊界條件遞歸前進段遞歸返回段。當邊界條件不滿足時,遞歸前進;當邊界條件滿足時,遞歸返回。

帕斯卡三角: 從遞推開始理解

帕斯卡三角.jpg

在中國 帕斯卡三角楊輝三角,因為在中國 楊輝三角 的記錄比歐洲 帕斯卡三角記錄早了幾百年。

能產生遞歸的條件

  1. 調用自身:以最小的函數處理問題,產生的新問題與原問題有着相同的形式。
  2. 遞歸出口:遞歸考慮有限的問題,出口就是遞歸調用最後一次調用的出口

遞歸與循環的區別

循環是滿足一定條件,重複執行同一段代碼片段。而遞歸是函數,不斷調用自己的行為。常見有 for-in/for-of 循環,而遞歸常見的有數學問題:fibonacci 函數。

缺點

  • 耗內存,可以使用尾回調

回溯(Backtrack)

一個遞歸調用的過程,就是回溯。

回溯是一種算法思想,它是用遞歸實現的。

用一個比較通俗的説法來解釋遞歸和回溯: 我們在路上走着,前面是一個多岔路口,因為我們並不知道應該走哪條路,所以我們需要嘗試。嘗試的過程就是一個函數。 我們選擇了一個方向,後來發現又有一個多岔路口,這時候又需要進行一次選擇。所以我們需要在上一次嘗試結果的基礎上,再做一次嘗試,即在函數內部再調用一次函數,這就是遞歸的過程。 這樣重複了若干次之後,發現這次選擇的這條路走不通,這時候我們知道我們上一個路口選錯了,所以我們要回到上一個路口重新選擇其他路,這就是回溯的思想。

遞歸算法 (recursive algorithm)

在遞歸問題中,使用 JavaScript/Rust 做為示例,有幾個經典的問題

  • 數組求和
  • fibonacci 函數
  • JavaScript 中使用遞歸實現深拷貝
  • React-Router 遞歸實現配置 routes
  • Vue 中遞歸組件

經典的 fibonacci 函數示例

  • 經典的 Fibonacci JavaScript 實現

```js export default function fibonacci(n) { if (n < 0) throw new Error("輸入的數字不能小於 0"); if (n === 1 || n === 2) { return 1; } return fibonacci(n - 2) + fibonacci(n - 1); }

const fi = fibonacci(7); console.log(fi); ```

  • 經典的 Fibonacci Rust 實現(含測試)

```rs fn main() { println!("Hello, world!");

let f1 = fibonacci(1);
println!("{}", f1);

let f2 = fibonacci(2);
println!("{}", f2);

let f3 = fibonacci(3);
println!("{}", f3);

let f4 = fibonacci(4);
println!("{}", f4);

}

pub fn fibonacci(n: i32) -> u32 { if n < 0 { panic!("輸入的數字不能小於 0") };

if n == 1 || n == 2 {
    return 1
}

fibonacci(n - 2) + fibonacci(n - 1)

}

[cfg(test)]

mod tests { use crate::fibonacci;

#[test]
fn fibonacci1() {
    let result = fibonacci(1);
    assert_eq!(result, 1);
}

#[test]
fn fibonacci2() {
    let result = fibonacci(2);
    assert_eq!(result, 1);
}

#[test]
fn fibonacci3() {
    let result = fibonacci(3);
    assert_eq!(result, 2);
}

} ```

從求和到遞歸

```js // 循環 var sum = 0; for (var i = 1; i <= 10; i++) { sum += i; } console.log(sum);

// 遞歸 function sum(n) { if (n == 1) return 1; return sum(n - 1) + n; }

var amount = sum(10); console.log(amount); ```

```rs fn main() { println!("Hello, world!"); while_sum_fn(); }

fn while_sum_fn() { let mut sum = 0; let mut i = 0; while i <= 10 { sum += i; i += 1; println!("sum: {}", sum); } println!("{sum}") } ```

Rust for 循環與 js 中循環有很大的區別,此處 rust 使用 while 語句代替 JavaScript 中的 for 語句。

基礎深拷貝

考慮:原始數據類型+引用數據類型

js function deepClone(target) { const targetType = typeof target; if (targetType === "object" || targetType === "function") { let clone = Array.isArray(target) ? [] : {}; for (const key in target) { clone[key] = deepClone(target[key]); } return clone; } return target; }

問題:循環引用(通過內置 weakMap)

```rs function deepClone(target, map = new Map()) { const targetType = typeof target;

if (targetType === 'object' || targetType === 'function') {
    let clone = Array.isArray(target)?[]:{};
    if (map.get(target)) {
        return map.get(target);
    }

    map.set(target, clone);

    if(Object.prototype.toString.call(target) === '[object Date]'){
        clone = new Date(target)
    }

    if(
        Object.prototype.toString.call(target) === '[object Object]' ||
        Object.prototype.toString.call(target) === '[object Array]'
      ){
        for (const key in target) {
            clone[key] = deepClone(target[key],map)
        }
    }

    return clone;
}
return target;

} ```

然後深拷貝需要考慮眾多的 js 的數據類型(包括 es5+ 中新增的數據類型)。深拷貝缺點也非常明顯,對於大對象,可能非常佔用計算機資源。基於這個特點,React 社區針對 React 和 JavaScript 的誕生了不可變數據庫:

  • immer
  • immutable.js

不可變數據,每次修改之後,會得到一個新的數據(但是儘可能的複用了原來的數據),這樣彌補了深拷貝的數據時的性能問題。

react router 遞歸實現配置 route

jsx // 遞歸函數 const rotuerViews = (routerItems) => { if (routerItems && routerItems.length) { return routerItems.map(({ path, Component, children, redirect }) => { return children && children.length ? ( <Route path={path} key={path} element={ <Suspense fallback={<Loading />}> <Component /> </Suspense> } > {rotuerViews(children)} // 遞歸遍歷子路由 {redirect ? ( <Route path={path} element={<Navigate to={redirect} />}></Route> ) : ( <Route path={path} element={<Navigate to={children[0].path} />} ></Route> )} </Route> ) : ( <Route key={path} path={path} element={ <Suspense fallback={<Loading />}> <Component /> </Suspense> } ></Route> ); }); } };

vue 中實現 tree 組件的遞歸(組件中如何使用自己)

```vue

```

擴展:尾部遞歸(Tail Recursion)

尾遞歸,首先要搞明白什麼是尾部調用? 其實就是發生函數調用後,最後執行的語句是函數調用。尾遞歸,就是在函數最後(Tail)發生了函數的調用(但是調用的自己,就是尾部遞歸)。

尾遞歸在普通尾調用的基礎上,多出了2個特徵:

  1. 在尾部調用的是函數自身 (Self-called);
  2. 可通過優化,使得計算僅佔用常量棧空間 (Stack Space)。

  3. 一個實例

```js function tailFactorial(n, total) { if (n === 1) return total; return tailFactorial(n - 1, n * total); }

function factorial(n) { return tailFactorial(n, 1); }

factorial(5); // 120 ```

遞歸非常耗費內存,因為需要同時保存成千上百個調用記錄,很容易發生"棧溢出"錯誤(stack overflow)。但對於尾遞歸來説,由於只存在一個調用記錄,所以永遠不會發生"棧溢出"錯誤。

尾部遞歸有哪些問題?

空間優化策略:尾遞歸

遞歸調用的缺點就是保存的調用棧(call frame),

如何優化尾部遞歸?

函數發生尾部遞歸的時候,返回的結果相差不大,保存在棧裏面毫無意義。沒有意義我們就應該不需要發生這些東西。所以計算機就可以省出一些內容。

遞歸展開

還是以階乘為例:

js function fact(n) { if (n <= 0) { return 1; } else { return n * fact(n - 1); } }

6 * fact(5) 6 * (5 * fact(4)) 6 * (5 * (4 * fact(3)))) 6 * (5 * (4 * (3 * (2 * (1 * 1)))))) // <= 最終的展開

展開的特點是:函數並沒有真正的運行,需要較大的內存空間用於展開,如果內容過大就容易爆棧。

尾遞歸函數依然還是遞歸函數,如果不優化依然跟普通遞歸函數一樣會爆棧,該展開多少層依舊是展開多少層。不會爆棧是因為語言的編譯器或者解釋器所做了“尾遞歸優化”,才讓它不會爆棧的。

小結

  • 什麼是遞歸
  • 從楊輝三角可是遞推,到遞歸
  • 遞歸與循環的區別
  • 遞歸與回溯
  • 遞歸算法常見的經典問題以及在前端 ReactRouter/Vue-Tree 中封裝組件
  • 尾遞歸及其優化、遞歸展開

參考