# 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!