Recursively return an array of positions where i occurs in j

Question

I am not good at Java so I just would like to say in advance "THIS IS MY HOMEWORK" and please "DO NOT DO MY HOMEWORK", this is the very first homework on recursion so this is my first time. Having said that, these are the instructions of my homework but I am not sure the steps that I need to take in order to achieve the goal. All I need is a great guy/girl who can give me good details on how to finish my homework, kind of steps. I have read the book, checked some websites about recursion, but I feel that I need a little more help.

Write a recursive static method that, given two string s and t, returns an array of all positions where t occurs in s. For example, findLocations("Frances ran and ran", "ran") returns [1, 8, 16].

Answer 1

I would probably approach it like this:

1. Given the argumets inputString and substring, call index = inputString.indexOf(substring).

2. If the substring is not found (index = -1), you should return the empty array (new int[0]), since no occurrences of the substring exists in the inputString.

3. Otherwise the substring does exist, in which case you should do the following:

   1. Get the array of indexes for the remaining part of the string, using something like arr = findLocations(inputString.substring(index+1), substring)

   2. Adjust the indexes in arr by adding index to each element.

   3. return index, concatenated with arr.

Answer 2

As you will be recursing through the first string and actively adding indices, I would recommend using something mutable, such as a List.

As for your recursive method, here are some tips:

// Initialize results list first
// Start the search using index = 0 and your empty results list.
ArrayList<Integer> recurSearch(String input, String search, int index, ArrayList<Integer> results)

// Inside recurSearch() 
int index = inputString.indexOf(search string, index);
// Here check the index. If it equals -1, no more matches. Return your result List.
// If does not equal -1, add to result list and return findLocations() using index + 1.

I hope this makes sense. As you clearly want to tackle most of this problem yourself, I tried to include as little code as possible. I included my method signature as I hope this will point you in the right direction.