I am trying to find the first occurrence of a letter in a string. For example, p in apple should return 1. Here is what I have:
// Returns the index of the of the character ch
public static int indexOf(char ch, String str) {
if (str == null || str.equals("")) {
return -1;
} else if(ch == str.charAt(0)) {
return 1+ indexOf(ch, str.substring(1));
}
return indexOf(ch, str.substring(1));
}
It just doesn't seem to be returning the correct value.
I'll give you some hints:
-1?Your attempt was good, but not quite there. Here is a correct implementation based off yours:
public static int indexOf(char ch, String str) {
// Returns the index of the of the character ch
if (str == null || str.equals("")) {
// base case: no more string to search; return -1
return -1;
} else if (ch == str.charAt(0)) {
// base case: ch is at the beginning of str; return 0
return 0;
}
// recursive step
int subIndex = indexOf(ch, str.substring(1));
return subIndex == -1 ? -1 : 1 + subIndex;
}
There were two problems with your attempt:
In the else if part, you had found the character, so the right thing to do was stop the recursion, but you were continuing it.
In your last return statement, you needed to be adding 1 to the recursive call (if the character was eventually found), as a way of accumulating the total index number.
Here's another variation. Instead of calling substring you could modify the function a bit to pass the next index to check. Notice that the recursion is initiated with index 0. (You could actually start on any index. There is also some error checking in case the letter isn't found. Looking for x in apple will return -1.)
public static void main(String []args){
System.out.println("Index: " + indexOf('e', "apple", 0));
System.out.println("Index: " + indexOf('x', "apple", 0));
System.out.println("Index: " + indexOf('p', "Mississippi", 3));
System.out.println("Index: " + indexOf('p', "Mississippi", 908));
}
public static int indexOf(char ch, String str, int idx) {
// check for garbage data and incorrect indices
if (str == null || str.equals("") || idx > str.length()-1)
return -1;
// check to see if we meet our condition
if (ch == str.charAt(idx))
return idx;
// we don't match so we recurse to check the next character
return indexOf(ch, str, idx+1);
}
Output:
Index: 4 Index: -1 Index: 8 Index: -1
idx = indexOf(ch, str, ++idx); this makes me cringe. Why not return indexOf(ch, str, idx + 1)?idx + 1 is much better here. There's no reason to increment the idx variable.Well if we must use recursion then try this:
class RecursiveFirstIndexOf {
public static void main(String[] args) {
System.out.println(indexOf('p', "apple", 0));
}
static int indexOf(char c, String str, int currentIdx) {
if (str == null || str.trim().isEmpty()) {
return -1;
}
return str.charAt(0) == c ? currentIdx : indexOf(c, str.substring(1), ++currentIdx);
}}
Why not doing it straight forward?
public static void main(String[] args) {
String str = "abcdef";
for (int idx = 0; idx < str.length(); idx++) {
System.out.printf("Expected %d, found %d\n", idx, indexOf(str.charAt(idx), str, 0));
}
System.out.printf("Expected -1, found %d\n", indexOf(str.charAt(0), null, 0));
}
public static int indexOf(char ch, String str, int index) {
if (str == null || index >= str.length()) return -1;
return str.charAt(index) == ch ? index : indexOf(ch, str, ++index);
}
OUTPUT:
Expected 0, found 0
Expected 1, found 1
Expected 2, found 2
Expected 3, found 3
Expected 4, found 4
Expected 5, found 5
Expected -1, found -1
++variable when they apparently think variable + 1 is too many characters.first of all : Recursion has two pillars, Base Case and General Case.
Base Case (the termination point) is the one where Recursion terminates and General Case as the name implies is where the program keeps executing until it finds Base Case
you may try this example, where count is a global static variable
public static int indexOf(char ch, String str)
{
// Returns the index of the of the character ch
if (str == null || str.Equals("")) //Base Case
{
if (count != 0)
{
if(str.Length == 0)
return -1;
return count;
}
else
return -1;
}
else if (ch == str.CharAt(0)) //Base Case
return 1 + count;
count++;
return indexOf(ch, str.Substring(1)); //General Case
}
String.indexOf(int ch)?