Using recursion to find a character in a string

Question

I am trying to find the first occurrence of a letter in a string. For example, p in the 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 does not return the correct value.

Answer 1

Your attempt was good, but not quite there. Here is the correct implementation based on 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 part else ifyou found a character, so the right thing is to stop the recursion, but you continue it.

In your last return statement, you had to add 1 to the recursive call (if the character was found), as a way of accumulating a common index number.

Answer 2

:

• , . , , .
• , , .
• - , , -1?

Answer 3

. , . , 0. ( . , . x -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);
}

:

Index: 4
Index: -1
Index: 8
Index: -1

Answer 4

, , :

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);

}}

Answer 5

?

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);
}

:

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

Answer 6

First of all: The recursion has two columns, the Main example and the General case .

The basic example (the termination point) is where the recursion ends, and the general case , as the name suggests, is where the program continues to execute until it finds the basic example.

you can try this example where countis a global variablestatic

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
}