CODEWITHSUNDEEP
javarecursionfibonaccitail-recursion
Parzival
Parzival

Reputation: 11

Clarification on tail recursive methods

Is the following method tail-recursive?

I believe that it is not tail recursive because it relies on the previous results and so needs a stack frame, am I correct to state this?

public int[] fib(int n)
{
    
    if(n <= 1){
        return (new int[]{n,0});
    }
    else{
        int[] F = fib(n-1);
        return (new int[]{F[0]+ F[1], F[0]});
    }
}

Upvotes: 0

Views: 45

Answers (2)

Lajos Arpad
Lajos Arpad

Reputation: 76583

Yes, you are correct, since it does not end with a call to itself of the form of

return fib(somevalue);

To convert it into a tail-recursive version you could do something like

// Tail Recursive
// Fibonacci implementation
 
class GFG
{
    // A tail recursive function to
    // calculate n th fibonacci number
    static int fib(int n, int a, int b )
    {
         
        if (n == 0)
            return a;
        if (n == 1)
            return b;
        return fib(n - 1, b, a + b);
    }
     
    public static void main (String[] args)
    {
        int n = 9;
        System.out.println("fib(" + n +") = "+
                                 fib(n,0,1) );
    }
}

Code taken from https://www.geeksforgeeks.org/tail-recursion-fibonacci/

Upvotes: 0

Bohemian
Bohemian

Reputation: 425053

You are correct: It is not tail recursive because the last line is not of the form

return funcName(args);

Upvotes: 1

Related Questions