Can tail recursion apply to this code?

Question

I have a simple piece of code, that addresses this (poorly stated, out of place) question :

template<typename It>
bool isAlpha(It first, It last)
{
    return (first != last && *first != '\0') ? 
        (isalpha(static_cast<int>(*first)) && isAlpha(++first, last)) : true;
}

I'm trying to figure out how can I go about implementing it in a tail recursive fashion, and although there are great sources like this answer, I can't wrap my mind around it.

Can anyone help ?

EDIT

I'm placing the disassembly code below; The compiler is gcc 4.9.0 compiling with -std=c++11 -O2 -Wall -pedantic the assembly output is

bool isAlpha<char const*>(char const*, char const*):
    cmpq    %rdi, %rsi
    je  .L5
    movzbl  (%rdi), %edx
    movl    $1, %eax
    testb   %dl, %dl
    je  .L12
    pushq   %rbp
    pushq   %rbx
    leaq    1(%rdi), %rbx
    movq    %rsi, %rbp
    subq    $8, %rsp
.L3:
    movsbl  %dl, %edi
    call    isalpha
    testl   %eax, %eax
    jne .L14
    xorl    %eax, %eax
.L2:
    addq    $8, %rsp
    popq    %rbx
    popq    %rbp
.L12:
    rep ret
.L14:
    cmpq    %rbp, %rbx
    je  .L7
    addq    $1, %rbx
    movzbl  -1(%rbx), %edx
    testb   %dl, %dl
    jne .L3
.L7:
    movl    $1, %eax
    jmp .L2
.L5:
    movl    $1, %eax
    ret

It is worth noting that a decent optimizing compiler could already turn this into a tailcall, because if you get to the point where `isalpha(static_cast(*first))` is true then the return value from the function is `isAlpha(++first, last)`, which meets all of the requirements of being tailcall-eligible. (Caveat: If `It::~It()` has side-effects then it's unlikely that any compiler would be able to make a tailcall out of this function even if you implemented it in a way that makes the tailcall more explicit.) — cdhowie, Dec 13 '14 at 22:52
OP: The two assembly listings in your question are identical! Neither has a recursive call. — cdhowie, Dec 13 '14 at 23:47
@cdhowie Oh, I misread `call isalpha` for `call isAlhpa`; really sharp eye there. I should edit out some things then — Lorah Attkins, Dec 14 '14 at 07:16

score 3 · Accepted Answer · answered Dec 13 '14 at 22:56

3

To clarify cdhowie's point, the function can be rewritten as follows (unless I made a mistake):

bool isAlpha(It first, It last)
{
  if (first == last)
    return true;
  if (*first == '\0')
    return true;
  if (!isalpha(static_cast<int>(*first))
    return false;
  return isAlpha(++first, last);
}

Which would indeed allow for trivial tail call elimination.

This is normally a job for the compiler, though.

answered Dec 13 '14 at 22:56

500 - Internal Server Error

28,327
8
59
66

Ok, I thought mentioning a local of the "superstack" prohibits tail recursion. Isn't mentioning `first` in the recursive call a problem? – Lorah Attkins Dec 13 '14 at 22:56
1

No. I am not sure exactly what you are referring to here, but the main issue preventing this optimization is if something needs to be done to the result of the recursive call before the outer return. – 500 - Internal Server Error Dec 13 '14 at 22:58
2

@500-InternalServerError Or if the `first` and `last` objects have destructors with side-effects. If they do, the compiler cannot destruct them early because the as-if rule would prohibit it. – cdhowie Dec 13 '14 at 23:12

Can tail recursion apply to this code?

EDIT

1 Answers1