1

I have this program:

#include <iostream>
#include <vector>

int foo(std::vector<int> bar) {
    if (bar[0] == 0)
        return bar[0];
    else 
    {
        bar[0] -= 1;
        return foo(bar);
    }
}

int main() 
{
    std::vector<int> bar {9999999};
    std::cout << foo(bar);
}

Compile with x86-64 gcc 12.2 using the flag -O3 (here), it exit with code 139:

Program returned: 139

which means my program has a segmentation fault.

So is my program undefined behaviour, or that gcc fails to optimize my tail recursion?

Improve this question
4
  • 1
    Tail recursion optimizations is not a requirement of C++, but some compilers can do it in limited circumstances. Apparently GCC doesn't do it in this case. You really have to look at the generated assembly code to see it (which is very easy to do on the compiler explorer). And I recommend you read through the GCC documentation and find out in which cases (if any) it will be able to do tail-recursion optimizations. Commented Mar 6, 2023 at 11:18
  • 7
    int foo(std::vector<int> bar) -> int foo(std::vector<int> &bar) Commented Mar 6, 2023 at 11:21
  • 4
    It's not a tail call since the argument must be destroyed after the recursive call has returned (unless the compiler can prove that it's not necessary). It's very easy to write functions that look tail-recursive but aren't in C++. Commented Mar 6, 2023 at 12:03
  • C++ TCO is a voluntary optimization, just like inline functions and registered arguments. C++ is originally not designed for functional programming. See quuxplusone.github.io/blog/2021/01/09/tail-call-optimization Commented Sep 19, 2024 at 18:27
Related questions
303
Does Python optimize tail recursion?
522
Why does GCC generate 15-20% faster code if I optimize for size instead of speed?
738
What is the easiest way to initialize a std::vector with hardcoded elements?
Load 5 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.