Recursive Fibonacci in text WebAssembly

Question

I've been playing around with text WebAssembly and wanted to write a recursive Fibonacci number calculator.

I got a version that works but it uses a single branch if statement to check for the base case:

(module
 (export "fib" (func $fib))
  (func $fib (param $0 i32) (result i32)
  (if
   (i32.lt_s
    (get_local $0)
    (i32.const 2)
   )
   (return
    (i32.const 1)
   )
  )
  (return
   (i32.add
    (call $fib
    (i32.sub
      (get_local $0)
      (i32.const 2)
    )
   )
    (call $fib
      (i32.sub
       (get_local $0)
       (i32.const 1)
     )
    )
   )
  )
 )
) 

I tested this in wabt here: https://webassembly.github.io/wabt/demo/wat2wasm/

I tried to rewrite this using select conditional:

(module
       (export "fib" (func $fib))
     (func $fib (param $0 i32) (result i32)
            (select
                   (return
                    (i32.const 1)
                    )
                  (return
                   (i32.add
                    (call $fib
                          (i32.sub
                           (get_local $0)
                           (i32.const 2)
                           )
                          )
                    (call $fib
                          (i32.sub
                           (get_local $0)
                           (i32.const 1)
                           )
                          )
                    )
                   )
                (i32.lt_s
                 (get_local $0)
                 (i32.const 2))))
     )

This compiles to .wasm, but it does not run as expected, just returning the base case. I tried similar versions with if-then-else, but to no avail. Why would the result of a single-branch if be any different from a two-branch conditional?

Answer 1

You just gave me a reason to learn wasm. I can't yet answer your question about the single-branch if, but I can show you a working fib function.

(module
  (func $fib2 (param $n i32) (param $a i32) (param $b i32) (result i32)
    (if (result i32)
        (i32.eqz (local.get $n))
        (then (local.get $a))
        (else (call $fib2 (i32.sub (local.get $n)
                                   (i32.const 1))
                          (local.get $b)
                          (i32.add (local.get $a)
                                   (local.get $b))))))

  (func $fib (param i32) (result i32)
    (call $fib2 (local.get 0)
                (i32.const 0)   ;; seed value $a
                (i32.const 1))) ;; seed value $b

  (export "fib" (func $fib)))

Copy/paste to demo it here

const wasmInstance =
  new WebAssembly.Instance (wasmModule, {})

const { fib } =
  wasmInstance.exports

for (let x = 0; x < 10; x = x + 1)
  console.log (fib (x))

Output

0
1
1
2
3
5
8
13
21
34

For what it's worth, the implementation here is quite different than yours. Your program requires exponential computational time and space whereas the above program's requirements are linear.

This is evident by examining your use of (call $fib ...). In your program, a single call to $fib has the possibility to spawn two additional calls to $fib, which each have the possibility to spawn two more calls to $fib, and on and on. Above $fib2 only has potential to call itself once, at most.

---

Although it has a lesser performance, of course it is still possible to implement the exponential process

(module
  (func $fib (param $n i32) (result i32)
    (if (result i32)
        (i32.lt_s (local.get $n)
                  (i32.const 2))
        (then (local.get $n))
        ;; recursive branch spawns _two_ calls to $fib; not ideal
        (else (i32.add (call $fib (i32.sub (local.get $n)
                                           (i32.const 1)))
                       (call $fib (i32.sub (local.get $n)
                                           (i32.const 2)))))))

  (export "fib" (func $fib)))