ok so first i divided the problem into smaller problem and bigger problem , the smaller problem would be to make changes for the first 2 characters and bigger problem would be for recursion to handle rest of the string.
Here is my code :-
public static String formatDC(String s)
{
if(s.length()<=1)
{
return s;
}
char ch1=s.charAt(0);
char ch2=s.charAt(1);
String smallOutput=formatDC(s.substring(1));
if(ch1==ch2)
{
return ch1+""+ch2+smallOutput;
}
else
{
return ch1+""+ch2+smallOutput;
}
}
but i dint get the right output , i couldnt figure out why because the logic i thought behind this code was i will let recursion bring me the answer for rest of the string and once it does i will just check for the first 2 characters and if they are same i will and a "" in between and append ch1 and ch2 to the starting of the string , but did not get the desired output so i did dry run and figured out the issue here is the correct code:-
public static String formatDC(String s)
{
if(s.length()<=1)
{
return s;
}
char ch1=s.charAt(0);
char ch2=s.charAt(1);
String smallOutput=formatDC(s.substring(1));
if(ch1==ch2)
{
return ch1+"*"+smallOutput;
}
else
{
return ch1+""+smallOutput;
}
}
so what i want to ask is since with recursion we have to take a leap of faith and assume recursion will bring the right answer i did the same , but since all the time we cant assume the right answer , so we have to dry run draw the recursion tree and then figure out the answer ? am i right or am i missing something
Approach in recursion
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(formatDC(sc.next()));
}
public static String formatDC(String s) {
if (s.length() <= 1) {
return s;
}
char ch1 = s.charAt(0);
char ch2 = s.charAt(1);
String smallOutput = formatDC(s.substring(1));
if (ch1 == ch2) {
return ch1 + "*" + smallOutput;
} else {
return ch1 + "" + smallOutput;
}
}
}
recursive code is fine
- Obtain the result for substring starting at index 1. Store this in another string , say ‘ros’ .
- Check whether the first character of current string and first character of ros are same.
- If so return , add a " * " to the new result and concatenate as s[0] + " * " + ros.
- Else simply return s[0] + ros.
Your approach is correct. You divided the problem into correct bigger and smaller problems. What you are doing is absolutely correct.
Now, in a recursion question sometimes its very easy to visualize the answer and figure out the base cases and bigger,smaller problems. Sometimes it not that easy. So, for that you can take help of the sample test case. Or take any sample testcase which is base case + 1. And draw the recursion tree for that.
So, don’t dry run every time for every large test case. Just take the sample test case or basecase +1 testcase.
I hope that helps. 
