Lucas sequence in Python

A Lucas sequence is a number sequence with a recursive relationship between its numbers where each proceeding number is the sum of its two previous numbers. In this sequence, the ratio of successive terms eventually approaches the golden ratio, where the ratio of two terms equals the ratio of their sum to the larger of the two quantities.

In mathematical form, the sequence can be represented as follows:

$L_{n} = \begin{Bmatrix}<br>2 & \therefore n = 0\\ <br>1 & \therefore n = 1\\ <br>L_{n-1} + L_{n-2} & \therefore n > 1 <br>\end{Bmatrix}$

Relationship with the Fibonacci sequence

The Lucas sequence is very familiar to the Fibonacci series, especially regarding calculating the proceeding value. Lucas sequence has a different starting value, but its values can be formed by adding two Fibonacci sequence values that share a common adjacent value.

Let's see how the Lucas sequence is formed using the Fibonacci sequence values to understand the relation and code the sequence in Python.

Iterative approach

In this example, we will use a for loop to iterate over the index positions specified in the code and calculate the subsequent terms.

Code explanation

• Line 2: Define an iterative function lucasSeq() to create a Lucas sequence and pass the terms count as a parameter.

• Lines 4–7: Define the return values for index values 0 and 1.

• Line 10: Create a temporary list tempSeq and save the first two values in it.

• Line 13–15: Create a for loop from index 2 to index + 1 and calculate the nextTerm for the corresponding index by adding the value on the index - 1 and index - 2 from the tempSeq.

• Line 15: Add the calculated value to the tempSeq list using append().

• Line 16: Return the obtained tempSeq to the driver code.

• Line 20: Set an index value that represents the number of Lucas sequence terms we want to output on the console.

• Line 21: Call the iterative function lucasSeq() by sending the index value as a parameter and saving the returned results in the mySeq instance.

• Line 22: Print the obtained Lucas sequence on the console using print().

Recursive approach

In this example, we will use divide the problem into smaller chunks and then call the lucasSeq() function recursively until the base case is satisfied and returns the calculated sequence.

Code explanation

• Line 2: Define a recursive function lucasSeq() to create a Lucas sequence and pass the terms count as a parameter.

• Lines 4–.7: Define the base case for index values 0 and 1.

• Line 9: Calculate the subsequent term by recursively calling the lucasSeq() with index - 1 and index - 2 as parameters and adding the returned values.

• Line 12: Set an index value that represents the number of Lucas sequence terms we want to output on the console.

• Line 13: Create a list comprehension mySeq and call the recursive function lucasSeq() for each i value in the defined range().

• Line 14: Print the obtained Lucas sequence on the console using print().

Memoization approach

In this example, we will optimize the recursive approach by using memoization which is often helpful in scenarios where the problem at hand is being solved multiple times.

Code explanation

• Line 2: Define a recursive function lucasMemo() to create a Lucas sequence and pass the terms count and a memo dictionary as parameters.

• Lines 3–8: Define the base case for index values 0 and 1 and for the value existing in the memo dictionary.

• Line 9: Calculate the subsequent term by recursively calling the lucasMemo() with index - 1 and index - 2 along with the memo dictionary as parameters and adding the returned values.

• Line 10: Return the value in the memo dictionary on the specified index value once the recursive calls are executed and returned.

• Line 13: Set a length value that represents the number of Lucas sequence terms we want to output on the console.

• Line 14: Create a list mySeq and call the recursive function lucasMemo() for each i value in the defined range().

• Line 15: Print the obtained Lucas sequence on the console using print().

Summary

All three approaches work well to obtain a Lucas sequence; however iterative approach has space complexity $O(1)$ while the recursive approach and memoization approach has time complexity $O(n)$ because a new list is created in each. The iterative approach is more efficient in terms of time. It is comparatively easier to understand as it has an explicit control flow. On the other hand, the recursive approach has a more clean and efficient code, and the memoization code is an even more optimized version.