CODEWITHSUNDEEP
javarecursion
anilhr2learn
anilhr2learn

Reputation: 31

How does this particular recursion works

How does this particular recursion works return (X.charAt(m-1) == Y.charAt(n-1) ? count(X, Y, m-1, n-1) : 0) + count(X, Y, m-1, n) 

in the below code?

The below code will return the count of number of times the pattern appears in a given string as a subsequence.

class Subsequence {
    public static int count(String X, String Y, int m, int n) {
        if (m == 1 && n == 1)
            return X.charAt(0) == Y.charAt(0) ? 1 : 0;
        if (m == 0)
            return 0;
        if (n == 0)
            return 1;
        if (n > m)
            return 0;

        return (X.charAt(m - 1) == Y.charAt(n - 1) ? count(X, Y, m - 1, n - 1) : 0) + count(X, Y, m - 1, n);
    }

    public static void main(String[] args) {
        String X = "subsequence";//input String
        String Y = "sue";// pattern
        System.out.print(count(X, Y, X.length(), Y.length()));
    }
}

Upvotes: 0

Views: 80

Answers (3)

Hughsie28
Hughsie28

Reputation: 103

I believe it is called a "Ternary Operator", it is another way to do IF statements in a more compact way (ie if you do a load of them at the same time for readability). It has to have somewhere to give the return value (a variable or return statement for example)

As an example it can look like this

boolean test = (condition) ? true : false;

Which is the same as writing

boolean test;
if (condition) {
    test = true;
} else {
    test = false;
}

CodeHunter's answer is a good example of how the sample code you gave is turned back into an if statement.

What it is doing is: (Psuedo)

function recursiveCount(stringStart, stringEnd, startLocation, endLocation) {
    /* pre-checks */

    // Total will be how many times it loops (1 + 1 + 1 + 1 + 1 basically what it is doing)
    // If there is no more occurances of that string it adds 0 instead of 1, and the recursion breaks.
    return (total + recursiveCount(stringStart, stringEnd, nextStartLocation, nextEndLocation)
}

Upvotes: 0

OldCurmudgeon
OldCurmudgeon

Reputation: 65879

You will often find that renaming your variables properly and adding some clarification comments works wonders.

public static int count(String string, String pattern, int stringLength, int patternLength) {

    if (stringLength == 1 && patternLength == 1) {
        // Two length=1 strings -> if they are equal then they match - obviously.
        return (string.charAt(0) == pattern.charAt(0)) ? 1 : 0;
    }
    if (stringLength == 0) {
        // No more string to search - no-match.
        return 0;
    }
    if (patternLength == 0) {
        // No more pattern to search - MATCH!
        return 1;
    }
    if (patternLength > stringLength) {
        // Can never find a pattern longer than the string.
        return 0;
    }

    return ((string.charAt(stringLength - 1) == pattern.charAt(patternLength - 1)) ?
            // Both end with same character - recurse to keep matching.
            count(string, pattern, stringLength - 1, patternLength - 1)
            // Not match.
            : 0)
            // ADD any matches further down the string. 
            + count(string, pattern, stringLength - 1, patternLength);
}

Sadly the code is wrong somewhere - searching for sue in subsequence prints 7.

Upvotes: 0

CodeHunter
CodeHunter

Reputation: 2082

It works as below:

if(X.charAt(m-1) == Y.charAt(n-1))
    return count(X, Y, m - 1, n - 1);
else
    return 0;    //since no match found here

Now, the above code is breakage of the first line of your return statement that uses ternary operator. Don't think that this is the complete break down of this code.

So, once you got this statement, the next step would be call this function again to find any matching characters starting from m- in first string and from n in the pattern string since we need to still match the whole pattern right from the start. However, if we find a match, we are just proceeding to match remaining available characters in both pattern and the string.

But to be honest, there are many better ways to code the pattern matching algorithm as compared to this approach.

Upvotes: 1

Related Questions