Is this tail recursion even though a logical-and is present?

Question

I know this title is duplicated with Is this tail-recursion?, but this is different and I could not get a clue from the previous question. so I have to ask again.

The code:

int sum_n(int n, int *sum)
{
    return n && (*sum += n) && sum_n(n - 1, sum);
}

It is said(foreign language source) that, tail recursion have two features:

The function is self-called
Only constant stack space is needed

So are these two features the only key factors for judging tail recursion? And whether the logical operator && in return statement affects tail recursion or not?

Most of all, is the above code tail recursion?

I *think* it is, and it is a special case because of the presence of the `&&` operator. Since, regarding implementation details, the value of the LHS of the `&&` operation need not be preserved in order to compute the ultimate result, a (hypothetical) compiler could just emit a "jump if zero" instruction followed by the tail call (i. e. it could replace the frame of `sum_n(n, sum)` with that of `sum_n(n - 1, sum)`. — , Dec 23 '13 at 10:39
Relevant: http://stackoverflow.com/questions/8514962/short-circuited-operators-and-tail-recursion?rq=1 — user2864740, Dec 23 '13 at 18:35

cHao · Accepted Answer · 2013-12-23T10:49:55.893

As written, it's a bit iffy. Reason being, technically, the function should regain control in order to && the result to know what to return. (This is easily optimized away, though, and most compilers will probably do so.)

In order to make sure it's tail-recursive, simply avoid doing anything with the result other than returning it.

int sum_n(int n, int *sum)
{
    if (!(n && (*sum += n))) return 0;
    return sum_n(n - 1, sum);
}

score 3 · Answer 2 · answered Dec 23 '13 at 10:46

3

This very function, I think, is not a tail recursion.

First, I agree that, this following form is tail recursion:

int sum_n(int n, int *sum)
{
    int tmp = n && (*sum += n);
    if (!tmp)
        return 0;
    else
        return sum_n(n - 1, sum);
}

However the above function is not literally equivalent to your original one. The code you provide shall be equivalent to this:

int sum_n(int n, int *sum)
{
    int tmp = n && (*sum += n);
    if (!tmp)
        return 0;
    else
        return sum_n(n - 1, sum) ? 1 : 0;
}

The difference, is the return value of sum_n(n - 1, sum) could not be used directly as the return value of your function: it shall be casted from int to _Bool.

answered Dec 23 '13 at 10:46

starrify

14,307
5
33
50

this function will never return 1. Never – UmNyobe Dec 23 '13 at 10:51
@UmNyobe Right, it will never return 1. Is that affect anything? – lulyon Dec 23 '13 at 10:58
I am not quite agree with you about the equivalent code. For equivalency, I think the else clause should be `return tmp && sum_n(n - 1, sum);` – lulyon Dec 23 '13 at 11:02
@UmNyobe Of course it would never return 1. However that's the conclusion obtained by you, a human, after analyzing the function and the algorithm itself. Please think as you're a compiler, according to the language specifications. Thank you. – starrify Dec 23 '13 at 11:02
yes. Why shall it be equivalent to`return sum_n(n - 1, sum) ? 1 : 0;` ? Do you have something to back it up? – UmNyobe Dec 23 '13 at 11:02
1

@UmNyobe In the original code, the expression at the `return` statement is of type `_Bool`, and there's only one way I know of that converting an `int` to a `_Bool`, according to ISO/IEC 9899:1999. – starrify Dec 23 '13 at 11:04
@lulyon Well, I agree that the code you provide is correct. However if it's inside the `else` clause, (I guess) `a && b` shall be no different to `1 && b` or `b ? 1 : 0`. Thank you for pointing out this. – starrify Dec 23 '13 at 11:11

Shuo Chen · Answer 3 · 2013-12-23T18:23:08.333

Not talking about the academic definition of tail recursion, however, clang 3.3 does compile sum() as a loop, not recursion.

        .file   "tail.c"
        .text
        .globl  sum
        .align  16, 0x90
        .type   sum,@function
sum:                                    # @sum
        .cfi_startproc
# BB#0:
        testl   %edi, %edi
        je      .LBB0_6
# BB#1:                                 # %.lr.ph
        movl    (%rsi), %eax
        .align  16, 0x90
.LBB0_3:                                # =>This Inner Loop Header: Depth=1
        addl    %edi, %eax
        je      .LBB0_4
# BB#2:                                 # %tailrecurse
                                        #   in Loop: Header=BB0_3 Depth=1
        decl    %edi
        jne     .LBB0_3
# BB#5:                                 # %tailrecurse._crit_edge
        movl    %eax, (%rsi)
.LBB0_6:
        xorl    %eax, %eax
        ret
.LBB0_4:                                # %split
        movl    $0, (%rsi)
        xorl    %eax, %eax
        ret
.Ltmp0:
        .size   sum, .Ltmp0-sum
        .cfi_endproc

        .section        ".note.GNU-stack","",@progbits

compiled with command:

$ clang -c tail.c -S -O2

clang version:

$ clang -v
clang version 3.3 (tags/RELEASE_33/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix

This is an excellent point. I've thought the tail recursion is compiler independent and can be judged by language standard itself. However, only when compiling the code with specific compiler, the conclusion can be finally verified. Since compilers optimize the `&&` operation in return statement, we get difference conclusion, so It is really compiler-dependent. I've got the point that, if I have to make sure it is tail recursion, as @cHao said, simply avoid doing anything with the result other than returning it. — lulyon, Dec 24 '13 at 02:21

Is this tail recursion even though a logical-and is present?

3 Answers3