Is this tail-recursion?

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 (开发者_Go百科 not know right or wrong) and they both take many stacks running.

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".

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.