# Recursive Algorithm

Discussion in 'Software Development' started by zahrav, Feb 16, 2005.

Not open for further replies.

Joined:
Dec 19, 2004
Messages:
55
How would u go about writing a recursive algorithm to find the square root, without using */% in JAVA

2. ### brendandonhu

Joined:
Jul 8, 2002
Messages:
14,681
Homework?

Joined:
Dec 19, 2004
Messages:
55
yup...but i dont get how u cant use any other operators.
i know u need a base case and a recursive case in which the method would be called again
so the structure would be like:
if (...) //base case
else ... //recursive case call the method in here

Joined:
Apr 30, 2001
Messages:
2,636

Joined:
Dec 19, 2004
Messages:
55
ya task 3 seems very similar...ne ideas how to go about it?
public static int squareRoot (int value, int high, int low)
.
.
.
.

Joined:
Apr 30, 2001
Messages:
2,636
In c++, without using */%, you could do it non-recursively like this.

Code:
```#include <iostream>

using namespace std;

static unsigned sqrt(unsigned long val) {
unsigned long temp, g=0, b = 0x8000, bshft = 15;
do {
if (val >= (temp = (((g<<1)+b)<<bshft--))) {
g += b;
val -= temp;
}
} while (b >>= 1);
return g;
}

int main() {
cout << sqrt(16) << endl;
}
```
If you can apply that method to java and then make it recursive, you might have it.

Joined:
Dec 19, 2004
Messages:
55
lol thanks a lot for ure help...but only if i understood C++

i'll try to deduce some of it, and get some of the logic...possibly

Joined:
Apr 30, 2001
Messages:
2,636
Yeh, I understand and I don't want to confuse the situation by throwing in the wrong language, but I don't think anything in the function is too far off from the way java does it, but I would focus more on the method than anything else.

Now here's a c++ version that doesn't use */%, doesn't use any loops and uses recursion to get the square root. (looks a little sloppy since no loops were used.)

Maybe someone can convert that to java and maybe even clean it up a little or a lot.

Code:
```#include <iostream>

using namespace std;

void sqrt(unsigned long& g, unsigned long& b, unsigned long& bshft, unsigned long& val) {
unsigned long temp;
b >>= 1;
if (val >= (temp = ( ( (g << 1 ) + b) << bshft-- ))     ) {
g += b;
val -= temp;

} else {
sqrt(g,b,bshft,val);
}
}

unsigned long sqrt(const unsigned long& num) {
unsigned long temp;
unsigned long g = 0;
unsigned long b = 32768;
unsigned long bshft = 15;
unsigned long val = num;
if (val >= (temp = ( ( (g << 1 ) + b) << bshft-- )) ) {
g += b;
val -= temp;
}
sqrt(g,b,bshft,val);
return g;
}

int main() {
cout << sqrt(16) << endl;
}
```
I'll attempt to do that in java.

Joined:
Apr 30, 2001
Messages:
2,636
O.K. I tried it in java and couldn't get it to work at first. Didn't know you couldn't pass by reference. I then created a class to do it.

This is my first java program (besides hello world) so I'm not sure how evil the code is or if it's even proper.

Also, I didn't use the the SUN sdk. I used MinGW's gcj compiler to create an executable from the java code, so I can't guarantee the following code will compile for you. At any rate it's something for you to go on.

Code:
```public class Squareroot {

class GetSquareRoot {

long temp, g, b, bshft, val;

void sqrt() {
b >>= 1;
if (val >= (temp = ( ( (g << 1 ) + b) << bshft-- )) ) {
g += b;
val -= temp;

} else {
sqrt();
}
}

long sqrt(final long num) {
g = 0;
b = 32768;
bshft = 15;
val = num;
if (val >= (temp = ( ( (g << 1 ) + b) << bshft-- )) ) {
g += b;
val -= temp;
}
sqrt();

return g;
}

};

public static void main(String args[]) {
GetSquareRoot i = new GetSquareRoot();
System.out.println( i.sqrt(16) );
}
}
```

Joined:
Dec 19, 2004
Messages:
55
cool thanks for all ure help

Joined:
Apr 30, 2001
Messages:
2,636
Just remember, you'll still have to disect it and explain how and why it works.

As Seen On