$7.$ Consider the Lucas numbers:

Ln $=$ Ln$1+$ Ln$2,$ n $>1$; L$1=1$; L$0=2.$

a$)$ Write a recursive function to compute Ln using the above definition directly. Implement

your solution and print Li$5,$ where $0<=$ i $<=10,$ as output.

b$)$ Write a recursive function$/$procedure to compute Ln with time complexity O$($n$)($more

precisely, the time complexity should be O$($nA$($n$))$ when n is large, where A$($n$)$ is the

complexity of adding Ln$1$ and Ln$2).$ Implement your solution and print Li$20,$ where

$0<=$ i $<=25,$ as output. This program must be able to compute Ln precisely for n $<=500.$

Hint $1$:

Let Kn $=$

Ln

Ln$1$

: Kn $=$

$11$

$10$

$\backslash$times Kn$1,$ n $>=1$; K$0=$

$2$

$1$

With this formulation, design a recursive algorithm for Kn such that the algorithm will

return both Ln and Ln$1$ with input parameter n$.$

Hint $2$: Can you use a primitive type to store L$500?$

For programs in $7$ a$)$ and $7$ b$)$ of this question, you are NOT allowed to use Python. For

C$++$ and Java, you can only use primitive types