A Fibonacci complexity class

While working on a project that will come out soon, I developed an algorithm with strange asymptotic behavior. In one of the functions of the algorithm there was an arithmetic progression that had to be computed. It was not a big deal as it concerned small sets of numbers each time, at least that's what I thought.

So instead of using the formula of arithmetic progression, I just put a recursive function for it. Something like

int d = 1000;
public void progression(a){
    while(d>0){
         progression(a+1);
    }
    d--;

}
progression(0);

Where d was proportional to the input.

It worked fine, but it was slower than it should be. The reason was that the progression was computed quite a lot of times and eventually such a simple function was a huge computation burden. I was really surprised to discover that the asymptotic behavior of the algorithm could be described by the Fibonacci sequence.
So that, given n input the complexity of the algorithm was O(f(n)∙c), where f(n) is the n-th member of the Fibonacci sequence and c is constant.
After replacing the function with the formula of arithmetic progression the complexity became polynomial, thankfully. 

There are two remarks about all these.

An innocent, simple and naive function may become a problem. We have to be careful on how many times this function will be executed.

Although the first edition of the algorithm was not optimal, there comes the question. Could we define a Fibonacci complexity class? Perhaps even find problems in this class.