• Status: Solved
• Priority: Medium
• Security: Public
• Views: 222

# countX

Hi,

I am working on below challenge
http://codingbat.com/prob/p170371

Given a string, compute recursively (no loops) the number of lowercase 'x' chars in the string.

countX("xxhixx") → 4
countX("xhixhix") → 3
countX("hi") → 0
i was not clear on how to find the number of x using recursion? please advise
0
gudii9
• 14
• 6
• 2
2 Solutions

Commented:
Do you know what recursion is?
If so, tell us what you know about recursion, and we might be able to make sure your understanding is correct.
0

Author Commented:
http://introcs.cs.princeton.edu/java/23recursion/

The idea of calling one function from another immediately suggests the possibility of a function calling itself. The function-call mechanism in Java supports this possibility, which is known as recursion.
Your first recursive program. The "Hello, World" for recursion is the factorial function, which is defined for positive integers n by the equation
n!=n×(n−1)×(n−2)×…×2×1
n!=n×(n−1)×(n−2)×…×2×1
The quantity n! is easy to compute with a for loop, but an even easier method in Factorial.java is to use the following recursive function:
public static long factorial(int n) {
if (n == 1) return 1;
return n * factorial(n-1);
}
We can trace this computation in precisely the same way that we trace any sequence of function calls.
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120

0

Author Commented:
how to get base case for this challenge?
how to draw diagram like below all the way till base case

factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120
0

Commented:
This challenge is the same programming  problem as
https://www.experts-exchange.com/questions/28968901/countHi-challenge.html
how to get base case for this challenge?
The base case is
When you found all the "x"s  return 0.
You can use a String method to search for x.
0

Author Commented:
Return 1  or return 0?
0

Commented:
In the case of factorials, you'll return 1 (or alternatively return n when n == 1).  If you returned 0, then 0 would be multiplied by the other numbers which would always result in 0, but that's not how factorials work, so use 1.  When the other numbers are multiplied by 1 the result will not be changed, which is good.

In the case of counting, return 0 (or alternatively return n when n == 0).  0 will be added to the other numbers, which will not change the result, which is good.
0

Author Commented:
sure. let me try
0

Commented:
how to draw diagram like below all the way till base case
I couldn't do it that way. Here is what I wrote.
``````public class Fact{
public static void main(String[] args){
System.out.println(" factorial(5) equals " + factorial(5));
}
public static int factorial(int n) {
System.out.println(" factorial(" + n + ")");
if(n==1){
System.out.println(" return 1");
return 1;
}
System.out.println(" return " + n + " * factorial(" + (n-1) + ")");
return n * factorial(n-1);
}
}
``````
My output:
factorial(5)
return 5 * factorial(4)
factorial(4)
return 4 * factorial(3)
factorial(3)
return 3 * factorial(2)
factorial(2)
return 2 * factorial(1)
factorial(1)
return 1
factorial(5) equals 120
0

Author Commented:
``````package com.solution;

import java.io.*;

public class CountX {
public static void main(String args[]) {
String Str = new String("xxhixx");

System.out.print("Return Value :");
System.out.println(Str.substring(1));
/*
* System.out.print("Return Value :" );
* System.out.println(Str.substring(10, 15) );
*/
System.out.println(countX("value is" + countX("xxhixx")));
}

public static int countX(String str) {
if (str.length() == 0){
return 0;
};
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
};
else {
return countX(str.substring(1));}

}
}
``````

above gives below error at line 25

Syntax error on token "else", delete this token

0

Author Commented:
``````package com.solution;

import java.io.*;

public class Count8 {
public static void main(String args[]) {
String Str = new String("xxhixx");

System.out.print("Return Value :");
System.out.println(Str.substring(1));
/*
* System.out.print("Return Value :" );
* System.out.println(Str.substring(10, 15) );
*/
System.out.println("value is" + count8(8818));
}

public static int count8(int n) {
//public int count8(int n) {
if (n < 1) return 0;
if (n % 10 == 8 && (n / 10) % 10 == 8) return 2 + count8(n/10);
else if (n % 10 == 8) return 1 + count8(n/10);
else return count8(n/10);
}
}
/* else {
return count8(n/10);
}*/
/* if(n % 10 == 8){
if(next digit is 8)return 2 + count8(n / 10);
else return 1 + count8(n / 10);*/

``````
``````public int countX(String str) {

if (str.length() == 0){
return 0;
};
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
};
else {
return countX(str.substring(1));

}

return 1;

}
``````
i see i made a stupid mistake of putting ; next to } of if block above passed all tests
0

Author Commented:
``````public int countX(String str) {

if (str.length() == 0){
return 0;
};
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
}
else {
return countX(str.substring(1));

}

//	return 1;

}
``````

i wonder why same code in eclipse gives wrong result

``````package com.solution;

import java.io.*;

public class CountX {
public static void main(String args[]) {
String Str = new String("xxhixx");

System.out.print("Return Value :");
System.out.println(Str.substring(1));
/*
* System.out.print("Return Value :" );
* System.out.println(Str.substring(10, 15) );
*/
System.out.println(countX("value is" + countX("xxhixx")));
}

public static int countX(String str) {
if (str.length() == 0) {
return 0;
}
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
} else {
//else {
return countX(str.substring(1));
//}
}

// return 1;

/*
* if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
* return 1 + countX(str.substring(1)); }; else { return
* countX(str.substring(1));
*
* }
*
* return 1;
*/

/*
* public int countX(String str) {
*
* if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
* return 1 + countX(str.substring(1)); } else { return
* countX(str.substring(1));
*
* }
*/

// return 1;

}

}
``````
Return Value :xhixx
0
0

Commented:
Your logic in your method was fine.  It works like the following.
``````import java.io.*;
public class X {
public static void main(String args[]) {
String inputStr = new String("xxhixx");
System.out.println(" value is " + countX(inputStr));
}
public static int countX(String str) {
if (str.length() == 0){
return 0;
}
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
}
else {
return countX(str.substring(1));}

}
}
``````
0

Commented:
My solution was a little different.
``````public int countX(String str) {
int index = str.indexOf("x");
if(index == -1) return 0;
else return 1 + countX(str.substring(index + 1));
}
``````
0

Author Commented:
``````package com.solution;

import java.io.*;

public class CountX {
public static void main(String args[]) {
String Str = new String("xxhixx");

// System.out.print("Return Value :");
// System.out.println(Str.substring(1));
/*
* System.out.print("Return Value :" );
* System.out.println(Str.substring(10, 15) );
*/
System.out.println(countX("value is" + countX("xxhixx")));
}

public static int countX(String str) {
if (str.length() == 0) {
return 0;
}
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
} else {
// else {
return countX(str.substring(1));
// }
}

// return 1;

/*
* if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
* return 1 + countX(str.substring(1)); }; else { return
* countX(str.substring(1));
*
* }
*
* return 1;
*/

/*
* public int countX(String str) {
*
* if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
* return 1 + countX(str.substring(1)); } else { return
* countX(str.substring(1));
*
* }
*/

// return 1;

}

}
``````

what is difference between above not working code and below working coe
``````package com.solution;

import java.io.*;

public class CountX2 {
public static void main(String args[]) {
String inputStr = new String("xxhixx");
System.out.println(" value is " + countX(inputStr));
}

public static int countX(String str) {
if (str.length() == 0) {
return 0;
}
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
}

else {
return countX(str.substring(1));
}

}
}
``````

eclipse also aligned it differently with else block. I used beyondcompare for text comparison but could not notice any difference to my eyes?
compare.png
0

Commented:
``````		System.out.println(countX("value is" + countX("xxhixx")));
``````
That is wrong. It should be
``````System.out.println(" value is " + countX(inputStr));
``````
0

Author Commented:
System.out.println(countX("value is" + countX("xxhixx")));

Select all

Open in new window
That is wrong. It should be
System.out.println(" value is " + countX(inputStr));

i could not catch even after using beyondcompare. how to make my eyes, brain as sharp as yours?
what is the difference of passing inputStr or passign directly value of inputStr which is xxhixx

To me both seems one and the same?
0

Author Commented:
``````package com.solution;

import java.io.*;

public class CountX {
public static void main(String args[]) {
String Str = new String("xxhixx");

// System.out.print("Return Value :");
// System.out.println(Str.substring(1));
/*
* System.out.print("Return Value :" );
* System.out.println(Str.substring(10, 15) );
*/
System.out.println(countX("value is" + countX(Str)));
}

public static int countX(String str) {
if (str.length() == 0) {
return 0;
}
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
} else {
// else {
return countX(str.substring(1));
// }
}

// return 1;

/*
* if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
* return 1 + countX(str.substring(1)); }; else { return
* countX(str.substring(1));
*
* }
*
* return 1;
*/

/*
* public int countX(String str) {
*
* if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
* return 1 + countX(str.substring(1)); } else { return
* countX(str.substring(1));
*
* }
*/

// return 1;

}

}
``````

above also gives 0?
0

Commented:
how to make my eyes, brain as sharp as yours?
We(coders) have all been there. Sometimes we can't see something right in front on our faces. One time I spent 4 hours looking for a error that was just a simple capitalization mistake. I can't explain it. It is just a occupational hazard.
what is the difference of passing inputStr or passign directly value of inputStr which is xxhixx

To me both seems one and the same?
It is the same.
above also gives 0?
You still have
``````System.out.println(countX("value is" + countX(Str)));
``````
Where you should have
``````System.out.println("value is" + countX(Str));
``````
0

Author Commented:
You still have
System.out.println(countX("value is" + countX(Str)));

Select all

Open in new window
Where you should have
System.out.println("value is" + countX(Str));

i used countX two times
0

Author Commented:
occupational hazard.
like this word
0

Author Commented:
``````package com.solution;

import java.io.*;

public class CountX {
public static void main(String args[]) {
String Str = new String("xxhixx");

// System.out.print("Return Value :");
// System.out.println(Str.substring(1));
/*
* System.out.print("Return Value :" );
* System.out.println(Str.substring(10, 15) );
*/
System.out.println("value is" + countX(Str));
}

public static int countX(String str) {
if (str.length() == 0) {
return 0;
}
if (str.charAt(0) == 'x') {
return 1 + countX(str.substring(1));
} else {
// else {
return countX(str.substring(1));
// }
}

// return 1;

/*
* if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
* return 1 + countX(str.substring(1)); }; else { return
* countX(str.substring(1));
*
* }
*
* return 1;
*/

/*
* public int countX(String str) {
*
* if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
* return 1 + countX(str.substring(1)); } else { return
* countX(str.substring(1));
*
* }
*/

// return 1;

}

}
``````

above finally works
0

Author Commented:
gives below output
value is4
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Featured Post

• 14
• 6
• 2
Tackle projects and never again get stuck behind a technical roadblock.