title: Recursion Problem - given array n and a number k
body: <p>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).</p>
  
  <p>I would like to count how many combinations of sorted numbers I can place in the array.</p>
  
  <p>For example :</p>
  
  <p>If <code>n = 3, max = 2</code>.(the only numbers we can use is 1/2 as max is 2) so there are 4 combinations of sorted arrays</p>
  
  <pre><code> 1. {1,1,1}
   2. {1,1,2}
   3. {1,2,2}
   4. {2,2,2}
  </code></pre>
  
  <p>I wrote some code and succeed to pass this specific example but any other example that <code>max &gt; 2</code> doesn't return the correct answer.</p>
  
  <p>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.</p>
  
  <p>my code :</p>
  
  <pre><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 &gt; max) {
          return 0;
      }
      if (numToMax &lt; 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);
  }
  </code></pre>