Recursive formula does not work as intended

Question

For my cs class Ive been given the following task. I have n different beers, and the i'th beer has a price of p[i]. the prices are: p1 = 2, p[2] = 3, p[3] = 2, p[4] = 1, p[5] = 4. I also have c coins, and I wish to figure out how many ways I can spend all the money on beers, with n = 5, and c = 5.

I know that there are 4 possible ways I can spend the money, (p1,p[2]), (p1,p[3],p[4]), (p[2],p[3]), (p[4],p[5]).

The task is to write a recursive formula, for the number of ways I can spend all my c money.

For now, I have this recursive formula: N(C,i) = \begin{cases} 0 &\text{if C $<$ 0 or i $<$ 0 }\\ 1 &\text{if C = 0}\\ N(C,i-1)+N(C-p_i,i) & \text{otherwise} \end{cases}

The formula basically calls itself repeatedly until either c=0, where it returns 1 (as it has exactly spend all its money), or if c < 0 or I < 0, it returns 0 as it has spend more money than it has, and therefor isn't valid.

But I'm not sure if it's correct. I tried writing the formula as code, but it returns 11 when it should return 4.

def fn(c,i):
    if(c < 0 or i < 0):
        return 0
    if(c == 0):
        return 1
    return fn(c,i-1)+fn(c-p[i-1],i)

I could really use some help, if someone can see if my recursion formula is wrong, or my code is wrong.

I hope I haven given the necessary information, or else I gladly answer all questions.

Answer 1

Almost your version, however, this yields the correct answer for your test case (assuming zero indexing for the function input).

def rec(c, i):
  global p
  if c == 0:
    return 1
  if i < 0 and c != 0:
    return 0
  return rec(c, i - 1) + rec(c - p[i], i - 1)

Do you see your mistake?