# Fibonacci数列的和式表达及wat实现

By [Aulee](https://paragraph.com/@aulee) · 2024-08-29

---

设数列的第$$n$$项为$$f(n)$$，则根据定义有$$f(n)=f(n-1)+f(n-2)$$。由此易得，

$$f(n) = f(1) + f(0) + f(1) + … + f(n-2)$$

用wat语言（wasm）可实现求和法计算$$f(n)$$如下：

    (module
        (func $fib (export "fib") (param $n i32) (result i32)
            (local $tmp i32)
            
            (local.set $tmp (i32.const 1))
            
            (block $break
                (br_if $break (i32.lt_s
                                    (local.get $n)
                                    (i32.const 2)))
                (loop $loop
                    (local.set $tmp (i32.add
                                        (call $fib (i32.add
                                                        (local.get $n)
                                                        (i32.const -2)))
                                        (local.get $tmp)))
                    (br_if $loop (i32.gt_s
                                    (local.tee $n (i32.add (local.get $n) (i32.const -1)))
                                    (i32.const 1)))
                )
            )
    
            local.get $tmp        
    
        )
    )
    
    直接用f(n)=f(n-1)+f(n-2)的逻辑，wat代码为：
    (module
        (func $fib (export "fib") (param $n i32) (result i32)
            (local $tmp i32)
            
            (local.set $tmp (i32.const 1))
            
            (block $break
                (br_if $break (i32.lt_s
                                    (local.get $n)
                                    (i32.const 2)))
                (local.set $tmp (i32.add
                                        (call $fib (i32.add
                                                        (local.get $n)
                                                        (i32.const -2)))
                                        (call $fib (i32.add
                                                        (local.get $n)
                                                        (i32.const -1)))))
            )
            local.get $tmp        
        )
    )

---

*Originally published on [Aulee](https://paragraph.com/@aulee/fibonacci-wat)*