CODEWITHSUNDEEP
crecursiontail-recursiontail-call-optimizationtail-call
Anne Ross
Anne Ross

Reputation: 39

Tail recursion [C]

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?

Upvotes: 3

Views: 155

Answers (1)

Deduplicator
Deduplicator

Reputation: 45694

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.

Upvotes: 2

Related Questions