2

What I interpreted from the below program is that it is tail recursive because at the end when the function returns, there is nothing left to evaluate. Am I right? 

void fun(int x) 
{ 
  if(x > 0) 
  { 
     fun(--x); 
     printf("%d\t", x); 
     fun(--x); 
  } 
}
Jaspreet Singh
  • 307
  • 1
  • 2
  • 7
  • Related: [What is tail-recursion?](https://stackoverflow.com/questions/33923/what-is-tail-recursion). In general, tail recursion is equivalent to looping, and the thing that throws a wrench in those gears in your posted code is the lead-in recursive call. Without that, there is little doubt this would be a textbook tail-recursion. Is that the area you're questioning? – WhozCraig Dec 15 '18 at 02:41
  • 1
    The second call to `foo()` is tail recursion. The first call isn't. – AlexP Dec 15 '18 at 02:53

2 Answers2

2

IMHO, it is not a tail recursion.

The key difference it that in tail recursion, we calculate the value first then we do the recursion, which means we don't need to keep the recursion stack. Whileas in a non-tail recursion, we do the recursion first and then we calucualte. So we have to store the recursion stack before we can calcualte finally.

In your case, before we reach the end of the first recursion, we cann't execute the print step, which make we have to store the x value in the stack. If the first recursion call is removed it should be a tail recursion.

Update:

according to https://en.wikipedia.org/wiki/Tail_call, a tail-recursion should be refer to a call. If we talk about tail-recursion on a function call's point, the first call in your program should be a non-tail-resursion one, while the second one is a tail-recursion call.

But for the whole program I think it is not a tail recursion one as a whole.

ZhaoGang
  • 4,491
  • 1
  • 27
  • 39
  • What I think people who ask about “tail recursion” really care about is what properties about a block of code we can prove. Here? The final call lets you perform tail-recursion optimizations and the first one doesn’t, so for example the function as a whole is not safe from an, *ahem*, stack overflow. – Davislor Dec 15 '18 at 18:15
  • I don’t think Wikipedia is an authoritative source for how we should use terms. Is there a better one? – Davislor Dec 16 '18 at 00:07
2

No. The first recursive call to fun() must save the current value of x, make a new function call, pass it a copy, and resume execution in the caller’s scope.

This isn’t counting angels on the head of a pin. Tail-recursion allows some very important compiler optimizations, such as being able to re-use the same stack frame and update all the parameter values in place. The non-tail call at the top cannot do that. If you want to prove an upper bound on how much stack space the function will need, you cannot.

It’s also true that the final call, and only that call, is tail-recursive. The compiler can perform tail-recursion optimization on it. Remove the first call, and the function is clearly tail-recursive.

Davislor
  • 14,674
  • 2
  • 34
  • 49
  • It's still tail recursion when it makes the second call. – Barmar Dec 15 '18 at 03:02
  • @barmar Sure, if it made just that second call, it would be tail-recursive. – Davislor Dec 15 '18 at 03:03
  • It's tail recursive even with the first call. That call isn't tail recursive, but the other one is. – Barmar Dec 15 '18 at 03:03
  • I consider "tail recursive" to be an attribute of a call, not the function as a whole. But I suppose if you're trying to determine whether the stack space used by the function will be bounded, you need to consider all the calls. – Barmar Dec 15 '18 at 03:05
  • @Barmar Yeah, when you’re trying to prove properties about “a tail-recursive function,” this one will not have those properties. – Davislor Dec 15 '18 at 03:11