Is this not tail recursive? (stack overflow error)

Question

This is a small function I have written to check whether an integer is a prime or not:

int prime(int x, int y = 2)
{
    if(y <= x/2)
    {
        if((x % y) == 0)
            return 0;
    }
    else
        return 1;

    return prime(x, ++y);
}

Now, I compile it with visual studio 2012, and if i give it a large value such as 105943, a stack overflow error occurs and the code breaks. Now, is this function not tail recursive? If so then a stack shouldn't be maintained for the recursive calls, and an overflow should not occur?

What am I not getting here exactly?

Yes, it is tail recursive, but the compiler you used didn't optimise the tail recursion to a loop. — Daniel Fischer
– Daniel Fischer, Commented Jun 19, 2013 at 16:09
@user1831704 The compiler should do it if you specify a high optimisation level (don't know how to do that in Visual Studio). (clang is happy with -O, gcc needs -O2 to make a loop of it) — Daniel Fischer
– Daniel Fischer, Commented Jun 19, 2013 at 16:17
I don't use that compiler, but this suggests that the tail call will be optimised at a suitably high optimisation level. — Mike Seymour
– Mike Seymour, Commented Jun 19, 2013 at 16:22
Or.. you could just write it as an iterative algorithm in the first place? Just a thought. — WhozCraig
– WhozCraig, Commented Jun 19, 2013 at 16:38
Just a remark, you don't have to get to x/2, you only need to verify till the square root of x. this way for x = 105943. you you will win 50 000 call to the function prime. — MBS
– MBS, Commented Jun 19, 2013 at 16:46

Tom Tanner · Accepted Answer · 2013-06-19 16:55:33Z

1

It is a tail recursive function, but there's no requirement for any compiler to optimise tail recursion into a loop. The chances are if you've got optimisation levels set high enough, it'll do so. But that's all.

LISP (and derived languages) are the only ones I know of where tail recursion is actually a requirement of the implementation.

answered Jun 19, 2013 at 16:55

Tom Tanner

9,3803 gold badges37 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Is this not tail recursive? (stack overflow error)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related