Creating recurrence equation of a simple recursive function

Question

If I was given the following recursive function, how would I create a recurrence equation for it?

QUIBBLE(n) {
   if n = 0 return 1; 
   else     return QUIBBLE(n-1) + QUIBBLE(n-1); 
}

I was thinking that it would be:

T(n):  2T(n-1) + 1 when n is >= 1
T(n) = 1 when n is 0, 

Answer 1

Well, a usual good starting approach is writing out the recurrence tree for some sample inputs.

Let's say n = 3

/* 1 call */   QUIBBLE(3)            
/* 2 calls */  = QUIBBLE(2) + QUIBBLE(2)
/* 4 calls */  = QUIBBLE(1) + QUIBBLE(1) + QUIBBLE(1) + QUIBBLE(1)
/* 8 calls */  = QUIBBLE(0) + QUIBBLE(0) + QUIBBLE(0) + QUIBBLE(0) + QUIBBLE(0) + QUIBBLE(0) + QUIBBLE(0) + QUIBBLE(0)
               = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
               = 8

By looking at the tree above we can see that with each function call, the tree splits into two branches.

This also shows us that the function QUIBBLE is clearly exponential and returns 2 ^ n

Now, your solution is nearly correct.

The one thing you don't need is the + 1 part of the equation when n >= 1.

T(n):  2T(n-1) + 1 when n is >= 1
//               ^
//                you don't need this

Here's a simple check to understand why. What is T(1) ?

Based on your equation, the answer is:

T(1) = T(0) + T(0) + 1 = 1 + 1 + 1 = 3

However, 2 ^ 1 == 2, not 3.

Therefore, the answer should be

T(n):  2T(n-1) when n is >= 1
T(n):  1 when n is 0