# Recursive Algorithm



## zahrav (Dec 19, 2004)

How would u go about writing a recursive algorithm to find the square root, without using */% in JAVA


----------



## brendandonhu (Jul 8, 2002)

Homework?


----------



## zahrav (Dec 19, 2004)

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


----------



## Shadow2531 (Apr 30, 2001)

Do you need to do something like in Task3 on this page, but with java instead?


----------



## zahrav (Dec 19, 2004)

ya task 3 seems very similar...ne ideas how to go about it?
public static int squareRoot (int value, int high, int low)
.
.
.
.


----------



## Shadow2531 (Apr 30, 2001)

In c++, without using */%, you could do it non-recursively like this.


```
#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.


----------



## zahrav (Dec 19, 2004)

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


----------



## Shadow2531 (Apr 30, 2001)

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.


```
#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.


----------



## Shadow2531 (Apr 30, 2001)

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.


```
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) );
    }
}
```


----------



## zahrav (Dec 19, 2004)

cool thanks for all ure help


----------



## Shadow2531 (Apr 30, 2001)

Just remember, you'll still have to disect it and explain how and why it works.


----------

