Write a recursive function (in Java) that will test to see if the input String p
ID: 3846426 • Letter: W
Question
Write a recursive function (in Java) that will test to see if the input String parameter belongs to the following format:
L = {S : S is in the form of AnB3n, for some n >= 0} where n and 3n are powers.
Test your function in main function.
----------------------------------------------------------------
The class should have two methods:
public static boolean IsIn(String w){ //body};
public static void main(String[] args)
----------------------------------------------------------------
Coding requirement:
public static void main(String[] args)
{
String str ="AABBBBBB";
if(IsIn(str))
System.out.println("The string " + str + " is in the language.");
else
System.out.println("The string " + str + " is in NOT the language.");
}
-----------------------------------------------------------------------------------------------------
• A recursive method calls itself.
IsIn(String w)
• Each recursive call, solves an identical, but smaller problem.
AABBBBBB
ABBB
• A test for the base case enables the recursive calls to stop
One of the smaller case?
w.length()==0
---------------------------------------------------------------------------------------------
Pseudocode
If base case == 0
return true
Else if check the characters
return IsIn(diminished string)
Else
return false
Explanation / Answer
public class IsInRecur
{
public static boolean IsIn(String w){
if ( w.length() == 0 ) //Base case, ie we reduced the string to size 0. Hence returns true.
{
return true;
}
else if ( w.contains( "ABBB" )) //Logical case, check if the string has AnB3n substring,
{
// if yes then we reduce ABBB from it recur, till we reduce it to length 0. (Base case)
System.out.println(w);
w = w.replace("ABBB","");
return IsIn(w);
}
else
{
// this is the case when the string doesnt match the format AnB3n, so return false.
return false;
}
}
public static void main(String[] args)
{
String str ="AAABBBBBBBBB";
if(IsIn(str))
System.out.println("The string " + str + " is in the language.");
else
System.out.println("The string " + str + " is in NOT the language.");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.