I'm trying to implement a recursive algorithm that counts all possible payment combinations for a given amount. I don't have much experience with recursion at all, so I would appreciate some help with this.
Available are the euro coins: 1 cent, 2 cent, 5 cent, 10 cent, 20 cent, 50 cent, 1 euro, 2 euro.
So I'm looking for the absolute value of the function that gives the linear combinations of the 8 coins for a given amount in cents.
The absolute value or the set of all those linear combinations can be split into two disjoint subsets, namely M1 which is the set of all linear combinations not containing coin n and the subset M2 in which coin n comes up at least once in every linear combination, this is equivalent to the following: 
To illustrate this here is an example for the amount of 5 cents, for which 4 different payment options exist, namely: five 1-cent coins, two 2-cent coins and one 1-cent coin, one 2-cent coin + three 1-cent coins, one 5-cent coin.
This is what I implemented in Java:
public class Coins {
static int[] c = { 1, 2, 5, 10, 20, 50, 100, 200};
static long M1 = 0;
public static long pay ( int m)
{
int n = c.length;
long M = pay(m, n);
return M;
}
private static long pay( int m, int n)
{
if ( n == 1)
{
return 1;
}
if ( m == 0)
return 1;
if ( m < 0)
return 0;
M1 += pay(m, n - 1) + pay(m - c[n-1], n);
return M1;
}
public static void main(String[] args) {
int m = 6;
long norm = pay(m);
System.out.println(norm);
}
}
This implementation does not give me the correct solution, and I'm not sure why it does not or what it's doing at all. I tried using print statements, for the case of m = 6, to give me intermediate results:
count = 1 m= 6 n= 8 M1= 0
count = 3 m= 6 n= 7 M1= 0
count = 5 m= 6 n= 6 M1= 0
count = 7 m= 6 n= 5 M1= 0
count = 9 m= 6 n= 4 M1= 0
count = 11 m= 6 n= 3 M1= 0
count = 13 m= 6 n= 2 M1= 0
count = 15 m= 6 n= 1 M1= 0
count = 16 m= 4 n= 2 M1= 0
count = 18 m= 4 n= 1 M1= 0
count = 19 m= 2 n= 2 M1= 0
count = 21 m= 2 n= 1 M1= 0
count = 22 m= 0 n= 2 M1= 0
count = 23 m= 1 n= 3 M1= 4
count = 25 m= 1 n= 2 M1= 4
count = 27 m= 1 n= 1 M1= 4
count = 28 m= -1 n= 2 M1= 4
count = 29 m= -4 n= 3 M1= 5
count = 30 m= -4 n= 4 M1= 13
count = 31 m= -14 n= 5 M1= 13
count = 32 m= -44 n= 6 M1= 13
count = 33 m= -94 n= 7 M1= 13
count = 34 m= -194 n= 8 M1= 13
Now it does actually count correctly in the sense that if you would add the cases in which m=0 and n=1, you would get the correct solution, but it somehow gets the result 13. Can anybody tell me what is going on here? Why does my implementation yield 13 as a result and not 5?
