Tail recursion [C]

Question

The question in my book is "Which of the recursive calls (not functions!) are tail recursive?"

unsigned f(unsigned x) 
{ 
    if(x==0) return 1; 
    else if(x==1) return f(x-1); 
    else return 3*x + f(x-1); 
}

In this example, I'm guessing that the first one is tail recursive, but the second one is not. However, what happens in the following case, where we also have printf() before and after the recursive call(s)?

void f(unsigned x) 
{
    if(x==0) return;
    else if(x==1) { f(x-1); printf("1"); }
    else if(x==2) { printf("2"); f(x-1); }
    else f(x-3);
}

Considering what I so far know about tail recursion, my guess was that the first one isn't, but the second and the third one are? Am I wrong, and if so, could you please explain how this works?

A recursive call is tail-recursive if the function immediately returns after making the call. — Barmar, Mar 30 '18 at 22:06
Note that in C++ tail recursion is not special according to the Standard. One _requirement_ imposed on implementations of a language to explicitly support tail calls that I know is http://www.schemers.org/Documents/Standards/R5RS/HTML/ — bipll, Mar 30 '18 at 22:07
Related: [What is tail recursion?](https://stackoverflow.com/a/37010) — Robert Harvey, Mar 30 '18 at 22:08
@bipll Question is tag C and Standard C don't guaranty tail recursion call too by the way. — Stargateur, Mar 30 '18 at 23:27

score 2 · Answer 1 · answered Mar 30 '18 at 22:44

In your first example, you are right that only the first call is potentially tail-recursive.

In the second example, the first call to printf() is potentially a tail-call, and the second and third call to f() are potentially tail-recursive.

It depends on the details of your implementation, and while the used ABI might give a hint (which is why the call to f() is more likely to be tail-recursive than the call to printf() a tail-call), that evidence is decidedly weak.
The standard is silent on those points.

You have to admire the certainty surrounding the issue. Certainly gives the compiler writers a bit of freedom to handle the cases as they like. — David C. Rankin, Mar 30 '18 at 22:52

Tail recursion [C]

1 Answers1