Time complexity of recursive algorithm (pseudo code)

If we have some code like this (pseudo) what is the time complexity of this recursive call? Assume that anything not stated below is considered constant time.

a,b,c > 0

//some code above, then we get here 

for i = 0 to a
    recursive(i,b)

//code continues

FUNCTION recursive(i,b)
if b = 0
    return 0

for j = i+c to a
    recursive(j,b-1)
ENDFUNC

EDIT I mainly am having trouble determining whether it is exponential or not. The depth is clearly b and does a calls in recursive function which gives O(b*a), but then the main loop also calls it a times which makes me think it should be in total: O(a^2 * b), but I don't quite understand how exponential complexity is generated so am wonder if it could be that instead?

Solution

First, let's look at two simple nested loops first:

for i (1..N) {
   for j (1..N) {
      f();
   }
}

for i (1..N) {
   for j (i..N) {
      g();
   }
}

f() is called N*N = N² = O(N²) times.

g() is called N+(N-1)+...+5+4+3+2+1 = N(N+1)/2 = N²/2 + N/2 = O(N²) times.

As you can see, it doesn't matter where the inner loop starts; the complexity is going to be the same.

Secondly, let's see what happens if you add a level of nesting.

for i (1..N) {
   for j (1..N) {
      for k (1..N) {
          h();
      }
   }
}

We already know the two outer loops are O(N²), and we are doing that N times, so we get O(N³). We can see that the exponent is the amount of nesting.

If we start unrolling recursive, we get

for i2 = i+c to a
    recursive(i2, b-1)

which is

for i2 = i+c to a
   for i3 = i2+c to a
       recursive(i3, b-2)

which is

for i2 = i+c to a
   for i3 = i2+c to a
       for i4 = i3+c to a
           recursive(i4, b-3)

etc

As you can see, you have b nested loops that iterate over a subset of a-c elements. Applying what we learned above, recursive takes O((a-c)^b) time.

The whole code (i.e. the call to recursive plus the outer loop) adds another layer, so it takes O((a-c)^b * a) time.