# Problem with a recursive function (check if a number is a perfect square)

-2

I'm trying to write, in CodeBlocks, a recursive function that check if a natural number (a long double) is a perfect square. This function called "Square" takes in input, by reference, the long double S and n (setted in the beginning at 1), a bool T and the long double to compare.

Here the code:

``````void Square(long double& S, long double& n, bool& T,long double k){
S=S+2*n+1;
n++;
if(S==k){
T=true;
}

if(S>k){
T=false;

}

if(S<k){
Square(S,n,T,k);
}
}
``````

And in the main function:

``````long double S,n,k;

bool T=false;

for(long double b=1;b<50000;b++){

for(long double a=1;a<b;a++){

S=1;
n=1;
T=false;

k=12*a*b*b*b-3*a*a*a*a;

Square(S,n,T,k);

if(T==true){
cout<<a<<"    "<<b<<"   "<<k<<endl;
}
}
}
``````

Sometimes occours this error: "Process returned -1073741571 (0xC00000FD)" (for example when (a = 108 and b = 121) and the program stops. Any help?

c++
codeblocks

1

Try this:

``````#include <cmath>

bool isPerfectSquare( long num ) {
long root = long(sqrt(float(num)));
return root * root == num;
}
``````

You'll get `True` if `num` is a perfect square or `False` if not.

1

You're probably getting a stack overflow error (which is when you use up the entirety of a thread's stack, and it crashes). If you compile with optimizations enabled, the compiler should be able to optimize `Square` so that it's tail-recursive, which will prevent the stack overflow error.

That being said, we can make `Square` shorter and friendlier to optimization by removing the references, and just calculating the multiplication directly (which is very cheap):

``````bool is_square(long long k, long long n = 0) {
if(n * n >= k)
return n * n == k;
else
return is_square(k, n + 1);
}
``````

With optimization turned on (use the `-O2` compiler flag for gcc and clang, or `/Ox` for msvc), this compiles to a simple loop:

``````is_square(long long, long long):
mov     rax, rsi
imul    rax, rsi
cmp     rdi, rax
jle     .L3
.L2:
mov     rax, rsi
imul    rax, rsi
cmp     rax, rdi
jl      .L2
.L3:
cmp     rdi, rax
sete    al
ret
``````

### Fast solution using `cmath` library:

``````#include <cmath>

bool is_square(long long k) {
long double real_root = sqrt((long double)k);
long long integral_root = llround(real_root);
return integral_root * integral_root == k;
}
``````

User contributions licensed under CC BY-SA 3.0