What is the recurrence if the base case is O(n)?

Question

We have to create an algorithm and find and solve its recurrence. Finding the recurrence has me stumped..

foo(A, C)
  if (C.Length = 0)
    Sum(A)
  else
    t = C.Pop()
    A.Push(t)
    foo(A,C)
    foo(A,C)

Initially A is empty and C.Length = n. I can't give the real algorithm because that's not allowed.

My instructor told me that I might try to use 2 variables. This is what I came up with:

T(n, i) = { n                if i =  0
            2*T(n, i-1) + C  if i != 0

I couldn't solve it, so I also tried to solve a recurrence with just one variable:

T(n) = { n0                  if n =  0
         2*T(n-1) + C        if n != 0

Where n0 is the initial value of n.

How do you form a recurrence from an algorithm where the complexity of the base case is O(n)?