I am trying to write a recursive function that checks if one word matches the reverse word but im not sure if its recursion

user_10505204 0
Viewed 269

All I really need to know is if the function I am using is recursive or if the method simply doesnt get called within itself. In my code, I have a helper function to reverse the second word and I put a toLowerCase in order to be able to compare words even if there are any random capitals. Is this recursion or is it just a function that compares the two?

import java.util.Scanner;

public class isReverse {
    public static void main(String[] args) {
        isReverse rev = new isReverse();
        Scanner in = new Scanner(System.in);
        System.out.println("Please enter a word: ");
        String a = in.nextLine();
        System.out.println("Please Enter a second word to compare: ");
        String b = in.nextLine();
        System.out.println(rev.isReverse(a, b));

    }
String rev = "";
    public boolean isReverse(String wordA, String wordB){
        String fword = wordA.replaceAll("\\s+", "").toLowerCase();
        String clean2 = wordB.replaceAll("\\s+", "").toLowerCase();
        String reverse = revString(clean2);
        if(fword.length() == 0){
            return false;
        }
        if (fword.equals(reverse)){
            return true;
        }
        if (!reverse.equals(fword)){
            return false;
        }

        else
        return  isReverse(fword,reverse);
    }

    public String revString(String sequence) {
        String input = sequence;
        StringBuilder order = new StringBuilder();
        order.append(input);
        order = order.reverse();
        rev = order.toString();
        return rev;
    }
}
recursion java
3 Answers

As far as your question is concerned, your code is not behaving like a recursive function because your code is not entering into the last else condition. For recursion to work you need to have:

  • a base case(if there is no base case the recursion will go on forever)
  • a recursive case(this is where you kind of reduce the original problem)

But my comment about your code:

If you're doing the actual reverse logic you don't need to use recursion just to check if the original string and the reverse string are the same. These is purely an algorithm problem so here is the way to solve the problem:

  • If the length of the given input is 1 then the reverse is the same.
  • else:
    • check the first and last chars of the string, if they are equal, then you need to remove those two chars and check if the rest of the string is a palindrome. This is the actual recursive step.
    • else the string is not a palindrome.
user_81147400

Technically? Well, you are calling a method from within itself, so, technically, yeah.

Pragmatically? No. The recursive call part will never be invoked.

Your code does this: I have 2 words. If the words are equal to each other, stop and do something. if they are not equal to each other, stop and do something. Otherwise, recurse.

And that's where it falls apart: It'll never recurse - either the words are equal, or they are not.

The general idea behind a recursive function is three-fold:

  1. The method (java-ese for 'function') calls itself.
  2. Upon each call to itself, the parameters passed are progressing to an end state - they become smaller or trend towards a stop value such as 0.
  3. There are edge cases where the function does not call itself, and returns instead (the answer for the smallest/zero-est inputs does not require recursion and is trivial).

You're missing the #2 part here. Presumably, this is what you'd want for a recursive approach. Forget about revString, delete that entirely. Do this instead:

  1. If both inputs are completely empty, return true (That's the #3 - edge cases part).
  2. If one of the two inputs is empty but the other one is not, false. (Still working on #3)
  3. If the first character of the input string is NOT equal to the last character of the output string, false. (Still #3).
  4. Now lop the first char off of the first input and the last off of the latter (Working on #2 now - by shortening the strings we're inevitably progressing towards an end no matter what)
  5. now call ourself, with these new lopped-down strings (That'll be #1).

That would be a recursive approach to the problem. It's more complicated than for loops, but, then, recursive functions often are.

user_7686440

Actually this is not a recursing. All you need is just:

  1. Check that both string have the same length
  2. Iteratively check letters from 0 to n from the first string and from n to 0 from the second string. If they equal, then go to the next iteration (recutsion) or return fail otherqwise.
// here do not check signature of the public method
public static boolean isReverse(String one, String two) {
    return isReverse(one, 0, two, two.length() - 1);
}

// support method has two additional counters to check letters to be equal
private static boolean isReverse(String one, int i, String two, int j) {
    if (i == one.length())
        return j == -1;
    if (j == two.length())
        return i == -1;
    // if not equal, then strings are not equal
    if (one.charAt(i) != two.charAt(j))
        return false;
    // go to the next recursion to check next letters
    return isReverse(one, i + 1, two, j - 1);
}
user_34613970
Related