1

I am studying tail recursion and I am not sure I am getting the definition right.

I saw this post's best answer (link) and am wondering if the method sum(int x, int num) is considered tail-recursive in the following example:

public class tailrecusiontest {

    private static int total;

    private static int add(int num)
    {
        total+=num;
        return total;
    }

    public static int sum(int x, int num) //THIS METHOD TAIL-RECURSIVE?
    {
        if(num == 0)
        {
            return x;
        }

        return sum(add(num), num-1);
    }


    public static void main(String[] args) {
        System.out.print("" + sum(0,4));
    }
}

I.e: What is stopping me to create an object and have call a method ( add(int num) in my example) that will handle the data, give back an output and, by definition, call it the method tail-recursive?

I am asking this question because an assignment is asking me if I can make a method "tail-recursive", and wonder how far the definition of tail-recursion extends.

This means that I can create any method and pass in the values then call it tail-recursive

Community
  • 1
  • 1
JohnMadon1234567890
  • 108
  • 1
  • 8
  • I think you're missing the point; whether a function is tail recursive doesn't depend on what the parameters are, or what anything in the parameters might do. – awksp Sep 29 '15 at 22:26
  • If anything, you could treat `add(num)` just like `n - 1` for the purposes of determining whether `sum` is tail-recursive – awksp Sep 29 '15 at 22:27
  • 1
    The second answer in the post you linked might be of more use. Try what it suggests. – awksp Sep 29 '15 at 22:28

2 Answers2

3

Your method meets the definition of tail recursion, but Java itself does not have the tail recursion optimization. That means that you will still have a N-sized stack and return through it 1 by 1.

mvd
  • 2,596
  • 2
  • 33
  • 47
1

In simplistic terms, tail recursion is a type of recursion where the recursive call is the final instruction in the function.

Based on that simple definition, your sample code is tail recursive because the recursive call is the last instruction.

That said, this question feels like a duplicate since you're essentially asking what tail recursion is and several posts on SO have done justice to that. For further reading on tail recursion see 'What is tail recursion'.

Community
  • 1
  • 1
pelumi
  • 1,530
  • 12
  • 21
  • I am sorry if you feel the post is a duplicate. I saw that post that you linked, I was just unsure if there were other restrictions to the definition of tail-recursive, that were not specified in all of the posts I read (which all use primitive data types). Thanks for the clarification. – JohnMadon1234567890 Sep 29 '15 at 22:35
  • 1
    @JohnMadon1234567890 no worries, I'm glad you've found an answer to your question. – pelumi Sep 29 '15 at 22:50