As per my answer in Write a recursive function that reverses the input string, I've tried seeing whether clang++ -O3
or g++ -O3
would make a tail-recursion optimisation, using some of the suggestions from How do I check if gcc is performing tail-recursion optimization?, but it doesn't look like any tail recursion optimisation is taking place. Any idea why?
Does this have to do with the way C++ objects are created and destroyed? Is there any way to make it work?
The programme:
% cat t2.cpp
#include <iostream>
#include <string>
std::string
rerev1(std::string s)
{
if (s.empty())
return s;
return rerev1(s.substr(1)) + s[0];
}
std::string
rerev2(std::string s, std::string b = "")
{
if (s.empty())
return b;
return rerev2(s.substr(1), s[0] + b);
}
int
main()
{
std::cout << rerev1("testing") << std::endl;
std::cout << rerev2("testing") << std::endl;
}
The testing (if the tail recursion optimisation would have been taking place, I'd expect there'd only be one call to each version of the function, not two):
% clang++ -Wall -O3 t2.cpp
% objdump --disassemble a.out | fgrep rerev | fgrep callq
400d8f: e8 ac ff ff ff callq 400d40 <_Z6rerev1Ss>
400fd1: e8 5a ff ff ff callq 400f30 <_Z6rerev2SsSs>
401168: e8 d3 fb ff ff callq 400d40 <_Z6rerev1Ss>
40128d: e8 9e fc ff ff callq 400f30 <_Z6rerev2SsSs>
% g++ -O3 t2.cpp
% objdump --disassemble a.out | fgrep rerev | fgrep callq
400c93: e8 28 02 00 00 callq 400ec0 <_Z6rerev1Ss>
400cfa: e8 11 03 00 00 callq 401010 <_Z6rerev2SsSs>
400f25: e8 96 ff ff ff callq 400ec0 <_Z6rerev1Ss>
4010ca: e8 41 ff ff ff callq 401010 <_Z6rerev2SsSs>
% clang++ -v
Debian clang version 3.0-6.2 (tags/RELEASE_30/final) (based on LLVM 3.0)
Target: x86_64-pc-linux-gnu
Thread model: posix
% g++ --version
g++ (Debian 4.7.2-5) 4.7.2
Copyright (C) 2012 Free Software Foundation, Inc.