Is tail call optimization applicable to this function?

Question

If bar calls bar(i/2) if i is an even integer and bar(3*i + 1) otherwise, the recursive function bar would tail-recursion.

const int bar(const int i) 
{
  if (i < 2) return i;
  return i % 2 ? bar(i/2) : bar(3*i + 1);
}

However, what if bar calls either bar or foo, who has a completely different set of local variables from bar?

const int bar(const int i) 
{
  if (i < 2) return i;
  return i % 2 ? bar(i/2) : foo(3*i + 1);
  // where foo is very complicated recursive call that has 
  // 11 different user-defined/primitive type of
  // local variables that can't be optimized out
}

My understanding is tail recursion optimization will use caller's stack. The caller is already done with its local variables before calling the callee. So, the callee can reuse it. My understanding sounds fine when the caller and callee are the same function(e.g. foo calls foo, bar calls bar). However, if the stack size and layout are totally different, and the callees might be one of multiple different functions with different stack layout, what is going to happen?

Firstly, would it be tail recursion? (Now, I understand that tail "call" optimization might be applied to but not this is not tail "recursion.") Secondly, major compilers such as gcc, clang, etc, would optimize this kind of tail calls? (The answer seems yes.)

What if the callee (foo in the second code example) is much more complicated? If the callee and caller are calling each other (mutual recursion), is the call in my second code example would be tail-call-optimized? If the callee (e.g. foo) is a complicated recursive call that is definitely not a tail recursion and very hard for a compiler to reduce it to a loop or so, would it be still tail-call-optimized?

Whatever foo() does has no effect on bar(). If the compiler can optimise bar() for tail recursion it does not (at least in your scenario) have to worry about foo(). Supposed you called printf() - would that prevent tail recursion optimisation? — user2100815
Calling foo() from bar() is not recursion. So I fail to see the relevance. — Disillusioned
The optimisation you are talking about is "tail call optimisation". Although it is most useful with (mutual) recursion, it is in no way limited to that case. — rici
@naomik The question fails to demonstrate mutual recursion in its 'minimal example'. (Wishy washy vague hand-wavy expositions about foo() is not a substitute for demonstration.) So: What's your point? OP doesn't demonstrate any kind of recursion with foo(). So I still don't see the relevance. — Disillusioned

S.M. S.M. · Accepted Answer · 2018-03-21T03:06:10

Is tail recursion optimization applicable to this function?

Yes, the tail recursion optimization is applicable in your examples. Please look at assembler https://godbolt.org/g/cSpUZw for the second sample. The more progressive optimization applied. Recursion is replaced with a loop.

bar(int):
  cmp edi, 1
  jg .L12
  jmp .L6
.L15:
  sar edi
  cmp edi, 1
  je .L14
.L12:
  test dil, 1
  jne .L15
  lea edi, [rdi+1+rdi*2]
  jmp foo(int)
.L14:
  mov eax, 1
  ret
.L6:
  mov eax, edi
  ret

Is tail call optimization applicable to this function?

2 Answers