To get a trial key
fill out the form below
Team License (a basic version)
Enterprise License (extended version)
* By clicking this button you agree to our Privacy Policy statement

Request our prices
New License
License Renewal
--Select currency--
USD
EUR
GBP
RUB
* By clicking this button you agree to our Privacy Policy statement

Free PVS-Studio license for Microsoft MVP specialists
* By clicking this button you agree to our Privacy Policy statement

To get the licence for your open-source project, please fill out this form
* By clicking this button you agree to our Privacy Policy statement

I am interested to try it on the platforms:
* By clicking this button you agree to our Privacy Policy statement

Message submitted.

Your message has been sent. We will email you at


If you haven't received our response, please do the following:
check your Spam/Junk folder and click the "Not Spam" button for our message.
This way, you won't miss messages from our team in the future.

>
>
C++ Tail Recursion Using 64-bit variabl…

C++ Tail Recursion Using 64-bit variables

Jun 23 2015

I want to share with you a problem I run into comparing iterative and recursive functions in C++. There are several differences between recursion and iteration, this article explains the topic nicely if you want to know more. In general languages like Java, C, and Python, recursion is fairly expensive compared to iteration because it requires the allocation of a new stack frame. It is possible to eliminate this overhead in C/C++ enabling compiler optimization to perform tail recursion, which transforms certain types of recursion (actually, certain types of tail calls) into jumps instead of function calls. To let the compiler performs this optimization it is necessary that the last thing a function does before it returns is call another function (in this case itself). In this scenario it should be safe to jump to the start of the second routine. Main disadvantage of Recursion in imperative languages is the fact that not always is possible to have tail calls, which means an allocation of the function address (and relative variables, like structs for instance) onto the stack at each call. For deep recursive function this can cause a stack-overflow exception because of a limit to the maximum size of the stack, which is typically less than the size of RAM by quite a few orders of magnitude.

I have written a simple Fibonacci function as an exercise in C++ using Visual Studio to test Tail Recursion and to 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);
}

The last thing fib_tail does is calling itself so it should have a tail call at the end. Let's look at the generated assembly to check. For this purpose I compiled the program in Release mode, which uses the optimization option /O2. The assembly looks like this:

0332_TailRecursion_Part1/image1.png

Bingo. If you look close at the last line you'll see a JMP instruction instead of a CALL. In this case tail recursion is enabled, our Fibonacci function doesn't suffer from any stackoverflow exception because at assembly level it is simply translated into an iterative function.

Not happy of this result, I wanted to do some performance tests by increasing the input variable n in my Fibonacci function. I then opted to change the variable type, used in the function, from int to unsigned long long. I ran the program again and surprisingly I got a stackoverflow exception coming through!!! This is the new Fibonacci function:

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 have a look at the generated assembly again:

0332_TailRecursion_Part1/image2.png

As I expected there is no tail recursion anymore! Now instead of the expected JMP there is a CALL. The only differences between those two functions is using a 64bit variable instead of a 32bit. Question is: "Why the compiler cannot enable tail recursion for 64 bit variable?"

I then decided to compile my program in 64bit to see if the same behavior would occur. This is the generated assembly:

0332_TailRecursion_Part1/image3.png

And now surprisingly we have tail recursion enabled again!! With the aid of 64 bit registers (rax, r8, rcx, rdx) the caller and the callee share the same stack frame and the callee returns directly to the caller's caller.

I posted a question too on StackOverflow and it seems it could be a problem with the Microsoft C++ compiler. One of the answer on Stackoverflow states that other C++ compilers like clang don't suffer from this problem but I have to test it.

I put the solution example on GitHub, you can clone it and try yourself. I was told on Reddit and Stackoverflow as well that VS2013 Community Edition does not have this issue. I tried with VS2013 Ultimate but I noticed the same exact problem. I will try in the next few days to test GCC and compare the result.

See the Example project on GitHub.

I hope this can save you time when and if you need to see why tail recursion might have not been correctly handled by the compiler.

See you soon!

This article was originally published at Coding Adventures Blog. Republished by the author permission.

Popular related articles
How PVS-Studio Proved to Be More Attentive Than Three and a Half Programmers

Date: Oct 22 2018

Author: Andrey Karpov

Just like other static analyzers, PVS-Studio often produces false positives. What you are about to read is a short story where I'll tell you how PVS-Studio proved, just one more time, to be more atte…
PVS-Studio for Java

Date: Jan 17 2019

Author: Andrey Karpov

In the seventh version of the PVS-Studio static analyzer, we added support of the Java language. It's time for a brief story of how we've started making support of the Java language, how far we've co…
Free PVS-Studio for those who develops open source projects

Date: Dec 22 2018

Author: Andrey Karpov

On the New 2019 year's eve, a PVS-Studio team decided to make a nice gift for all contributors of open-source projects hosted on GitHub, GitLab or Bitbucket. They are given free usage of PVS-Studio s…
Technologies used in the PVS-Studio code analyzer for finding bugs and potential vulnerabilities

Date: Nov 21 2018

Author: Andrey Karpov

A brief description of technologies used in the PVS-Studio tool, which let us effectively detect a large number of error patterns and potential vulnerabilities. The article describes the implementati…
Static analysis as part of the development process in Unreal Engine

Date: Jun 27 2017

Author: Andrey Karpov

Unreal Engine continues to develop as new code is added and previously written code is changed. What is the inevitable consequence of ongoing development in a project? The emergence of new bugs in th…
Appreciate Static Code Analysis!

Date: Oct 16 2017

Author: Andrey Karpov

I am really astonished by the capabilities of static code analysis even though I am one of the developers of PVS-Studio analyzer myself. The tool surprised me the other day as it turned out to be sma…
The Last Line Effect

Date: May 31 2014

Author: Andrey Karpov

I have studied many errors caused by the use of the Copy-Paste method, and can assure you that programmers most often tend to make mistakes in the last fragment of a homogeneous code block. I have ne…
The Evil within the Comparison Functions

Date: May 19 2017

Author: Andrey Karpov

Perhaps, readers remember my article titled "Last line effect". It describes a pattern I've once noticed: in most cases programmers make an error in the last line of similar text blocks. Now I want t…
The way static analyzers fight against false positives, and why they do it

Date: Mar 20 2017

Author: Andrey Karpov

In my previous article I wrote that I don't like the approach of evaluating the efficiency of static analyzers with the help of synthetic tests. In that article, I give the example of a code fragment…
The Ultimate Question of Programming, Refactoring, and Everything

Date: Apr 14 2016

Author: Andrey Karpov

Yes, you've guessed correctly - the answer is "42". In this article you will find 42 recommendations about coding in C++ that can help a programmer avoid a lot of errors, save time and effort. The au…

Comments (0)

Next comments
This website uses cookies and other technology to provide you a more personalized experience. By continuing the view of our web-pages you accept the terms of using these files. If you don't want your personal data to be processed, please, leave this site.
Learn More →
Accept