[FIXED] Is it possible to calculate Lucas numbers recursively with time complexity O(n)?

Issue

I have a homework assignment to calculate Lucas numbers. How can I make my algorithm O(n) while still keeping it recursive?

This is the hint he gives:

href="https://i.stack.imgur.com/UAUn8.png" rel="nofollow noreferrer">

When thinking about the question I thought I would keep my main for loop and make it so that it stores the 2 numbers before the one computed but then that would be iterative.

This is my code right now:

lucas(n) {  
    return 2 if n = 0;
    return 1 if n = 1;
    return lucas(n - 1) + lucas(n - 2);
}
main(String args[]) {
    for (int i = 0; i<=10; i++)
        print(lucas(i*5));
}

(The code is written like that in case of plagiarism.)

Solution

Since this is homework, I will not post the solution as code, but I hope I can show the path to it.

The given hint uses a vector with 2 values - in Java we can use an array (since a method cannot return just two values). The method needs the value of n.

int[] calc(int n) {
    // TODO
}

The formula Gn = M X Gn-1 - M is the given matrix, and Gn = [An , Bn] (An = Ln and Bn = Ln-1) - can we rewritten as
[An , Bn] = [[1,1] [1,0]] X [An-1 , Bn-1] or

An = 1*An-1 + 1*Bn-1 = An-1 + Bn-1 and
Bn = 1*An-1 + 0*Bn-1 = An-1

The method would call itself with n-1, unless n == 0, to get [An-1,Bn-1] and then calculate the output array [An,Bn] using above formula.

Initial array, for n=0, should be [2,-1] (aka G0 in hint.)

(since Gn only depends on Gn-1 the pure recursive solution is O(n) - unlike the usual method to calculate the Lucas number where Ln depends on Ln-1 and Ln-2)

---

I have completely ignored the second hint and used int[] above - but don't forget to consider if an int will be able to represent L500
(having the hint is a sign that it will not)

Answered By - user16320675
Answer Checked By - Dawn Plyler (JavaFixing Volunteer)