What is the correct type for a recursive function

Let’s say I have a simple fibonacci function. The below code does not compile because of a type error of the return that returns the recursive function. What is the right type?

public func fibonacci(num: Nat) : async Nat {
        if(num < 2) {
            return 1
        } else {
            return fibonacci(num-1) + fibonacci(num - 2);
        }
    }

I had to write a private function. Is this the best way?

actor {
    
    public func getFib(num: Nat) : async Nat {
         fibonacci(num);
    };

    func fibonacci(num: Nat) : Nat {
        if(num==1)
            return 0;
        if (num == 2)
            return 1;
        
            return fibonacci(num - 1) + fibonacci(num - 2);
        
    };
};
2 Likes

I think since it is an async function, try: return await fibonacci(num-1) + await fibonacci(num - 2);

1 Like

Yes, it is, and this answer needs 20 characters.

1 Like

this approach returns syntax error [M0001], unexpected token 'await', expected one of token or <phrase> sequence: <exp_bin(ob)>

1 Like

Hmm, I will make sure to test it myself before I comment next time, thanks.

The result of the recursive calls are async, so you’d have to await them:

public func fibonacci(n : Nat) : async Nat {
  if (n < 2) {
    1
  } else {
    (await fibonacci(n - 1)) + (await fibonacci(n - 2))
  }
}

However, be aware that each recursive call through a public actor method is an asynchronous canister message send, so this will be horribly slow. For a recursive algorithm, your solution of doing the recursion in a synchronous helper function actually is waaaay better.

2 Likes

oh wow. It never occurred to me that it will make an external call. Thank you for the info!