登录·注册
文章详情
1
recursion vs loop
unordered
Recursion occurs when a thing is defined in terms of itself or of its type. wiki.
The source code of this article https://github.com/unordered/fibonacci

Fibonacci sequence

Fibonacci sequence is a classic example of recursion:
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n - 1) + Fib(n - 2)

Implement a Fibonacci with recursion

Use rust

First we need create a cargo project
cargo new --lib fibonacci
And config it build for wassembly.
// Cargo.toml
...

[lib]
crate-type = ["cdylib", "rlib"]

[dependencies]
wasm-bindgen = "0.2"
Implements fibonacci
// lib.rs

use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub fn fibonacci(n: u64) -> u64 {
    match n {
        0 | 1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}
Build for webassembly (we need to install wasm-pack first via cargo install wasm-pack)
wasm-pack build --release
target
pkg
├── package.json
├── fibonacci.d.ts
├── fibonacci.js
├── fibonacci.d.ts
└── fibonacci.wasm
Next we can exec the fibonacci function via js
// example/src/index.js
import('../../pkg/fibonacci')
  .then(mod => {
    console.time("rust recursive")
    console.log(mod.fibonacci('30'))
    console.timeEnd("rust recursive")
  })
The console output:
1346269n
rust recursive: 6.595703125ms

Use js

// example/src/index.js

function fibonacci (n) {
  if (n === 0 || n === 1) {
    return 1
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}

console.time("js recursive")
console.log(fibonacci(30))
console.timeEnd("js recursive")
The console output:
1346269
js recursive: 224.23095703125ms
It can be seen the rust is 34 times faster then js in this case.

Implementing a Fibonacci with loop

Use rust

// lib.rs

#[wasm_bindgen]
pub fn fibonacci_loop(n: u64) -> u64 {
    if n == 0 || n == 1 {
        return 1;
    }
    let mut num1 = 1;
    let mut num2 = 1;
    for _ in 2..(n + 1) {
        let tmp = num1 + num2;
        num1 = num2;
        num2 = tmp;
    }
    num2
}
After build we can exec the fibonacci_loop function via js
// example/src/index.js
import('../../pkg/fibonacci')
  .then(mod => {
    console.time("rust loop")
    console.log(mod.fibonacci_loop('30'))
    console.timeEnd("rust loop")
  })
The console output:
1346269n
rust loop: 0.234130859375ms

Use js

// example/src/index.js

function fibonacci_loop(n) {
    if (n === 0 || n === 1) {
        return 1
    }
    let num1 = 1
    let num2 = 1
    for (let i = 1; i < n; i++) {
        let tmp = num1 + num2
        num1 = num2
        num2 = tmp
    }
    return num2
}

console.time("js loop")
console.log(fibonacci_loop(30))
console.timeEnd("js loop")
The console loop:
1346269
js loop: 0.2578125ms

Summary

Calculate the result of the 30th Fibonacci number.
recursionloop
rust6.595703125ms0.234130859375ms
js224.23095703125ms0.2578125ms
It can be seen that the speed of rust and js is almost the same. So we should use loop instead of recursion whenever possible.