JAVA Write a recursive method static int intSquareRoot(int n) {} // return the b
ID: 3841723 • Letter: J
Question
JAVA
Write a recursive method
static int intSquareRoot(int n) {} // return the biggest number whose square is <= n. Assume n >= 0.
Use recursion. No loops allowed. You will need to recurse on n/4 rather than n-1. That's because the method is called with some big values . If you recurse on n-1 those values will generate a StackOverflowError.
Of course Math.sqrt() or other Math class methods are not to be used in your implementation. You're just coding this using recursion and elementary operations .
Implementation Hint: intSquareRoot(n) is close to intSquareRoot(n/4) * 2. (Either equal to it or one more than it. You can tell which one, by squaring something.)
Explanation / Answer
public class SquareRoot
{
public static void main(String args[])
{
int x =999 ;//Define number here to find the square root
System.out.println(intSquareRoot(x));
}
public static int intSquareRoot(int x)
{
// Do Binary Search for intSquareRoot(sqrt(x))
int start = 1, end = x, ans=0;
while (start <= end)
{
int mid = (start + end) / 2;
// If x is a perfect square
if (mid*mid == x)
return mid;
// Since we need floor, we update answer when mid*mid is
// smaller than x, and move closer to sqrt(x)
if (mid*mid < x)
{
start = mid + 1;
ans = mid;
}
else // If mid*mid is greater than x
end = mid - 1;
}
return ans;
}
}
Sample output:
3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.