Recursion Problem - given array n and a number k

Question

Given an array size n, and a positive number max(max represent the range of the numbers that we can use to place in the array).

I would like to count how many combinations of sorted numbers I can place in the array.

For example :

If n = 3, max = 2.(the only numbers we can use is 1/2 as max is 2) so there are 4 combinations of sorted arrays

 1. {1,1,1}
 2. {1,1,2}
 3. {1,2,2}
 4. {2,2,2}

I wrote some code and succeed to pass this specific example but any other example that max > 2 doesn't return the correct answer.

the problem as I identify it is when the recursion reaches the last index it doesn't try a third number it just folds back.

my code :

private static int howManySorted(int n, int max, int index, int numToMax, int prevNum) {        
    // If the value is bigger then max return 0
    if(numToMax > max) {
        return 0;
    }
    if (numToMax < prevNum) {
        return 0;
    }
    //If Index reached the end of the array return 1
    if(index == n) {
        return 1;
    }

    int sortTwo =  howManySorted(n, max, index+1, numToMax, numToMax);
    int sortOne =  howManySorted(n, max, index+1, numToMax+1, numToMax);
    return ((sortOne+sortTwo));
}

public static int howManySorted(int n, int max) {
    return howManySorted(n, max, 0, 1, 0);
}

Answer 1

start with "{1," and add elements "{1,1" and/or value "{2," with each recursion. when it reach n elements array we add to the counter. n is the number of elements in the array max is the maximal value for each element. minimal is 1. element is the current cell in the array being manipulated. we start with 1 (in actual array means 0). value is the current value of the current element. we start with 1.

// external function according to the given question
public static int count (int n, int max) 
{
    return count(n,max, 1, 1);
}

private static int count (int n, int max, int element, int value) 
{
    int counter = 0;
    // only if our array reached n elements we count the comination
    if (element == n) 
        counter++;
    else // we need to continue to the next element with the same value
        counter += count(n, max, element +1, value);
    if (value < max) // if our current element didn't reach max value
        counter += count (n, max, element, value+1); 
    return counter;
}