I just came across this piece of recursive code, as much as I can guess this should be an infinite recursion but somehow it executes and does terminate. Can anybody tell me how this happens and what will be it's time complexity ?

Integer overflow

I guess it somehow uses the overflow in the integer to terminate the recursion, not sure. Is the complexity going to be infinite ?

It's complexity is undefined, exactly as the behaviour of this shit code.

You have the code, print n before you call yourself. Don’t guess, debug.

@RantSomeWhere @nitwhiz it is a bad piece of code but somehow this was given in one of our university exams. I guess they just wanted the students to point out the error.

@gdsoumya so it’s your homework.

@broseph not at all. This was in a previous year question paper.

This code could terminate, not terminate or do anything because signed integer overflow is undefined behaviour in C / C++.

@RantSomeWhere u don't need an else block because only one of the returns should technically work so this is equivalent to a code with else block.

Why dont you use -o?

@HampusMa I didn't require a custom executable file, a.out was good enough in this case.

@gdsoumya okay. I personally find it more efficient with -o but it's personal preference.

Just as an aside

Even though you guys are correct in saying that integer overflow is not defined everything that happens can be easily explained

If you take the time to make an equation the value you are looking for becomes 2^n*99+1 mod 2^32=1

99 has no common divider with 2 so n>=32 and who could have guessed the 32nd value is a one

So even though the compiler is allowed to do whatever there is not much optimization going on it seems and it works out to be O(32) on your machine at least.

Integer overflow at its finest

Pretty clear how the recursion is ending, but still pretty cool!