Tail recursion in C ++ using 64-bit variables - Part 1

This time I want to share with you one problem I encountered when I decided to compare iterative and recursive functions in C ++. There are several differences between recursion and iteration: they are described in detail in this article . In general purpose languages ​​like Java, C, or Python, recursion is quite expensive compared to iteration because of the need to allocate a new stack frame each time. In C / C ++, these costs can be easily eliminated by telling the optimizing compiler to use tail recursion, in which certain types of recursion (or rather, certain types of tail calls) are converted into unconditional branch instructions. To perform such a conversion, it is necessary that the most recent action of the function before returning the value is a call to another function (in this case itself). In this scenario, the unconditional jump to the beginning of the second subprogram is safe. The main drawback of recursive algorithms in imperative languages ​​is that it is not always possible to have tail calls in them, i.e. allocating space for the address of a function (and its associated variables, for example, structures) on the stack for each call. If the recursion depth is too large, this can lead to a stack overflow due to the limit on its maximum size, which is usually orders of magnitude smaller than the amount of RAM.

As a test for studying tail recursion, I wrote in Visual Studio a simple Fibonacci function in C ++. Let's see how it works:

int fib_tail(int n, int res, int next) { if (n == 0) { return res; } return fib_tail(n - 1, next, res + next); } 

To get a tail call before returning a value, the fib_tail function calls itself as the last action. Let's now take a look at the generated assembler code. To do this, I compiled the program in release mode using the optimization / O2 key. This is what this code looks like:



There is! Notice the last line: JMP is used instead of the CALL instruction. In this case, tail recursion worked, and our function will not have any problems with stack overflow, since at the assembler level it turned into an iterative function.
')
This was not enough for me, and I decided to experiment with performance by increasing the input variable n . Then I changed the type of variables used in the function from int to unsigned long long . By running the program again, I suddenly got a stack overflow! This is how this version of our function looks like:

 typedef unsigned long long ULONG64; ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next) { if (n == 0) { return res; } return fib_tail(n - 1, next, res + next); } 

Let's look again at the generated assembly code:



As I expected, tail recursion was not here! Now, instead of the expected JMP used CALL . Meanwhile, the only difference between the two variants of our function is that in the second case I used a 64-bit variable instead of a 32-bit variable. In this connection, the question arises: why does the compiler not use tail recursion when using 64-bit variables?

I decided to compile the program in 64-bit mode and see how it behaves. Generated assembly code:



Here the tail recursion appeared again! Thanks to 64-bit registers (rax, r8, rcx, rdx), the calling and called functions have a common stack, and the called function returns the result directly to the call point inside the calling function.

I asked my question on StackOverflow - it seems that the problem is in the Microsoft C ++ compiler itself. The author of one of the comments said that this problem is not observed in other C ++ compilers, but I have to make sure of this myself.

I posted sample code on GitHub - you can copy it and try to run it. On Reddit and Stackoverflow, I was also told that in the VS2013 Community Edition, this problem does not occur. I tried to work in VS2013 Ultimate, but I ran into it there. Over the next few days I will try to test the code under GCC and compare the results.

See the Example project on GitHub .

I hope that my investigation will be useful for you, if you suddenly happen to understand why the compiler does not implement tail recursion in certain cases.

See you soon!

Continued: habrahabr.ru/company/pvs-studio/blog/261029