Look at the generated assembly code and see if it uses a call or jmp instruction for the recursive call on x86 (for other architectures, look up the corresponding instructions). You can use nm and objdump to get just the assembly corresponding to your function. Consider the following function:
int fact(int n)
return n <= 1 ? 1 : n * fact(n-1);
gcc fact.c -c -o fact.o -O2
# get starting address and size of function fact from nm
ADDR=$(nm --print-size --radix=d fact.o | grep ' fact$' | cut -d ' ' -f 1,2)
# strip leading 0's to avoid being interpreted by objdump as octal addresses
STARTADDR=$(echo $ADDR | cut -d ' ' -f 1 | sed 's/^0*\(.\)/\1/')
SIZE=$(echo $ADDR | cut -d ' ' -f 2 | sed 's/^0*//')
STOPADDR=$(( $STARTADDR + $SIZE ))
# now disassemble the function and look for an instruction of the form
# call addr <fact+offset>
if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \
grep -qE 'call +[0-9a-f]+ <fact\+'
echo "fact is NOT tail recursive"
echo "fact is tail recursive"
When ran on the above function, this script prints "fact is tail recursive". When instead compiled with -O3 instead of -O2, this curiously prints "fact is NOT tail recursive".
Note that this might yield false negatives, as ehemient pointed out in his comment. This script will only yield the right answer if the function contains no recursive calls to itself at all, and it also doesn't detect sibling recursion (e.g. where A() calls B() which calls A()). I can't think of a more robust method at the moment that doesn't involve having a human look at the generated assembly, but at least you can use this script to easily grab the assembly corresponding to a particular function within an object file.
Nave factorial and fibonacci functions are not good examples. Compilers are often subjected to dumb benchmarks with them, so compiler writers make sure to add special optimizations that apply specifically to functions that look like fact/fib.
@Adam Rosenfield: Your solution worked for me with a few minor changes. For example, I'm using C++, and my function is a member function, so the function name becomes something mangled like "_ZN5cycle4stepEib".
@Adam Rosenfield: I find it interesting that it makes that call tail-recursive at all with -O2. Meanwhile, with -O3 it "unrolls the loop" some 10 times, and then actually calls itself.
Just found this question and couldn't help but point out that the code isn't even tail recursive in nature, since the last operation in the function is actually multiplication, not the recursive call to fact.