Comment by Chinjut

Yes, because the number of calls in this setup is 2 * the next result - 1, and the Fibonacci sequence itself grows at this Θ(φⁿ) rate.