How can I solve this problem with recursion in Java?

Question

public static int[] generateNumbers(int start, int end) {
    // case for empty array
    if (start > end) {
        int returnEmptyArray[] = {};
        return returnEmptyArray;
    }

    // setting size of the result array
    if (start < 0) {
        int sizeOfArray = end - start - 1;
        int result[] = new int[sizeOfArray];
    }

    // setting size of the result array
    if (start > 0) {
        int sizeOfArray = end - start;
        int result[] = new int[sizeOfArray];
        return generateNumbers(start, end, 0, result);
    }

    return null;
}

// helping method for recursion
public static int[] generateNumbers(int start, int end, int i, int[] result) {
    i = start;
    if (i < end) {
        result[i] = i;
        i++;
    }

    return generateNumbers(start, end, ++i, result);
}

Hi everybody! I have tried everything I could imagine to solve this problem. This program should count upwards recursively from start to end and negative numbers should be included as well. In the end, the result should be put into an integer array. Examples: start: 2, end: 5 --> result = {2, 3, 4, 5} start: -4, end: 3 --> result = {-4, -3, -2, -1, 0, 1, 2, 3}

I would be really thankful for a code snippet and an explanation or at least an approach how I can solve this problem.

Answer 1

Instead of giving you a solution, I'll go through the reasoning how to find the solution.

[ We all fully understand that creating such an array of integers this way is meant as an exercise in recursive thinking, not to be done this way in production-quality software. ]

The main two questions for recursion are always:

• For a given task, like generateNumbers(3,7), how can I solve it by re-using the results of a "simpler" task of the same type?
• What is a task so simple that I want to solve it directly? And I should choose a case where I'll surely arrive when applying my simplification strategy from question 1.

One possible answer is (there are other possibilities):

• If I know the result of generateNumbers(3,6), I just have to append the 7 at the end, and then I got it. Generalized: Solving the question generateNumbers(start,end-1), and then appending end.
• If start is greater than end, the result is an empty array.

Implementing that is straightforward, with one quirk: appending something to an array isn't easy in Java. You can:

• Make the recursion more complicated, by first creating an array long enough to hold the final result, and in the recursive calls keep track of the position where to append the new number.
• Use the List data type instead of an array (if your course has covered that). Appending to a List is easy.
• Write an int[] append(int[] arraySoFar, int newValue) method, thus making the "append" step in the recursion easy. The method has to create a new array, one longer than the input, copy the input there, and insert the new value at the end.

Just to show you that there can be many different ways of using resursion for your problem, here are a few other approaches:

• Instead of reducing the end by one, and then appending the end number, you can increase the start by one and prepend the start number.
• For solving generateNumbers(3,7), you can find some number in the middle, e.g. 5, and solve by appending generateNumbers(3,5) and generateNumbers(6,7), meaning that you create the result of one generateNumbers() call by cleverly combining the results of two recursive calls.

Answer 2

 public static int[] generateNumbers(int start, int end) {
    int length = end - start + 1;
    
    if(length <= 0) {
        // throw an exception
    }
    
    int[] numbers = new int[length];
    generateNumbers(start, end, 0, numbers);
    return numbers;
 }
 
 public static void generateNumbers(int start, int end, int index, int[] numbers) {
    if(start > end) {
        return;
    }
    numbers[index] = start;
    
    generateNumbers(start + 1, end, index + 1, numbers);
 }

Answer 3

There are some quite odd parts in your code.

For example this:

 if (start < 0) {
     int sizeOfArray = end - start - 1;
     int result[] = new int[sizeOfArray];
 }

is pointless, you are creating local variables in if condition and never use them.

Your calculation of the sizeOfArray is wrong, it should be end - start + 1, also, there is no reason to check whether start is positive or negative, ditch it all. Then, remove return null, it's a dead code.

For your subroutine function, you can't just write into array on the same index as the number you are about to write, you will get ArrayIndexOutOfBoundsException. For example if your start is -4, you will basically (in the first call) attempt to do result[-4] = -4, which is obviously nonsence.

Better solution would be to hold index value in i (starting from 0) and adding this value to start: result[i] = start + i.

Also, the ++i call is wrong, as you call i++ right before it, so you are actually increasing i by 2 instead of 1.

Your subroutine also has no terminating condition - it can never end. Try to put it in format:

if(...) {
    ...
    return generateNumbers(...);
}
return result;

Btw, you will obviously need to edit your condition after changing what i does.