Is this tail-recursion?

Question

I wrote a function to calculate the power of an integer then take modulus. I wonder if what I did is tail recursion :

int takeModulusTAILRECURSION(int coef, int x, int n, int module){
        int result = 0;
        if ( n > 0 )
            result = takeModulusTAILRECURSION( mod(coef * x, module), x , n - 1, module  );
        else if ( n == 0)
            result = mod ( coef , module );
        return result;
    }

//take modul of an integer ( both negative and positive )
int mod(int x, int modul){
    while ( x < 0) 
        x += modul;
    return x % modul;
}

Here is another function using recursion purely, which I think is different from the above :

int takeModulusNORMRECURSION(int x, int n, int module){
    if ( n == 1 )
        return mod( x, module );
    else {
        int total = x * takeModulusNORMRECURSION( x, n - 1, module);
        return mod( total, module);
    }
}

By the way, anyone can show me how to check the frame stack in Eclipse in these cases ? as I tried ( not know right or wrong) and they both take many stacks running.

score 0 · Accepted Answer · edited May 23 '17 at 12:20

Whether this is tail recursion depends on how the code is compiled.

Tail recursion happens when you're directly returning a call to another function (possibly yourself). Tail call optimization (the reason people care about tail recursion) happens when the compiler/interpreter notices this, and just replaces the current stack frame rather than creating another. In your case, if it is compiled naively, you don't have tail recursion because you're making the recursive call, then assigning it to a variable in your call stack, which you later return. That assignment step means that you're doing additional stuff after calling the other function, which makes your code as it stands not a candidate for tail call optimization.

However a good compiler should rewrite your code like so:

int takeModulusTAILRECURSION(int coef, int x, int n, int module){
    if ( n > 0 )
        return takeModulusTAILRECURSION( mod(coef * x, module), x , n - 1, module  );
    else if ( n == 0)
        return mod ( coef , module );
    else
        return 0;
}

//take modul of an integer ( both negative and positive )
int mod(int x, int modul){
    while ( x < 0) 
        x += modul;
    return x % modul;
}

Now it is tail recursive.

But whether tail call optimization could happen now depends on the language and implementation. For example if your code is supposed to be Java, then as Does the JVM prevent tail call optimizations? points out, you aren't going to get tail call optimization no matter what you do.

Edit: I was saying "tail recursive" for "tail recursive and tail call optimized".

A function can be tail recursive even if the compiler/interpreter doesn't optimize it. "Tail call optimization" (or "tail recursion optimization"), rather than tail recursion itself, is what "happens" in that case. — Fred Nurk, Feb 19 '11 at 09:09
@fred-nurk: D'oh, you're right. That's what I get for trying to answer questions well past my bedtime. — btilly, Feb 19 '11 at 09:17
Wasn't your confusion there the reason you downvoted the other answer, which that new user has now deleted? — Fred Nurk, Feb 19 '11 at 09:22
@fred-nurk: It was, and I tried to reverse my vote (but couldn't), and tried to leave an apology for that user (but the post was deleted). :-( — btilly, Feb 19 '11 at 09:52

score 0 · Answer 2 · answered Mar 24 '11 at 20:12

0

The first method is tail recursive because when the function executes 'return', the value it returns is a value that does not depend on a call to another method at that time.

The second method is not tail recursive and in fact is not recursive whatsoever since it just iterates over changing values of x.

The third and final method is also tail recursive because, like the first example, when the method 'returns' it is able to do so without calling out to any method, including itself.

Hope this helps.

answered Mar 24 '11 at 20:12

Lloyd Moore

3,117
1
32
32

As a minor technicality pointed out by [the other answer](http://stackoverflow.com/a/5049870/1711796), the first isn't tail recursive, but it's easy to make it so. The third definitely isn't tail recursive - it's multiplying the returned result by `x` and calling `mod` between the recursive call and returning. Also, I don't believe the question is actually about the second method, that's just there for a more complete code sample. – Bernhard Barker Mar 10 '14 at 14:08

Is this tail-recursion?

2 Answers2

Linked