Fibonacci and Lucas Formulas in Python

Picture courtesy of geralt via Pixabay

Introduction

In this article, I’m going to give a brief introduction as to what recursion is, how it can be used to generate sequences of numbers, and how to perform some of these basic operations in Python. Two sequences of real numbers that will be pertinent to our discussion are the Lucas Numbers and the Fibonacci numbers.

Ultimately, recursion refers to the buildup of a sequence of numbers based on an explicit pattern that is given. This patten comes in the form of an equation known as the recurrence relation. Moreover, any sequence has to have a starting point, known as a base case. In other words, to generate an entire sequence, you must be given both a recurrence relation and a base case; we’ll illustrate some examples using Python.

Fibonacci and Lucas Numbers

Our first example is the Fibonacci Numbers. The first two numbers are F_1 = 1, F_2 = 1, and all numbers thereafter are generated with the recursive relation

F_n = F_{n-1} + F_{n-2}

The starting numbers 1 and 1 constitute the base case for this recursion. Without a base case we can’t figure out any numbers in the sequence, due to a phenomena called infinite recursion.

This sequence’s terms can also be found directly using a non-recursive formula based upon a constant called the golden ratio, though that has nothing to do with recursion, so I won’t discuss it further here.

Our other sequence of interest, the Lucas Numbers, illustrate another reason why base cases are important. The base cases are L_1 = 1 and L_2 = 3, and the numbers thereafter are generated with the recursive relation

L_n = L_{n-1} + L_{n-2}

Notice that if we took away the base cases, these sequences would for all purposes be identical. The recurrence relations are the same, apart from interchanging Fs with Ls! And that little thing is merely a naming convention!

Anyway, the heart of this article will be about coding up these recurrences in Python, so let’s walk through how to do that now.

Fibonacci and Lucas Numbers in Python

It turns out the Python code for finding Fibonacci Numbers versus Lucas Numbers is very similar. There are only a few important differences that I alluded to in the previous section. That being said, I’ll walk through some code to generate Fibonacci numbers in detail, and then show the similar code for Lucas numbers and discuss the differences.

Here is the code for Fibonacci numbers:

The input is a single natural number, n, and the output is the nth Fibonacci number. As before, we use the convention that F_1 = 1 and F_2 = 1 (so then F_3 = 2, F_4 = 3, and so on). In fact, the very first line after the function definition identifies these base cases as such.

After that, we create a list that is initially comprised of n zeros. The reason for this is that our algorithm will involve putting the Fibonacci numbers in a list as we identify them, up to the nth one. Since the first two Fibonacci numbers are 1 and 1, we designate the first two elements of listOfFibs to both be equal to 1. We know there are at least two elements in the list since n ≥ 3. If n were equal to 1 or 2, the function would have returned 1 before reaching this point. And of course, this code is not designed to work if n is not a natural number (this includes 0).

Now we have our for loop. We use the next several slots in listOfFibs to store the next Fibonacci numbers, determining those one at a time with the recurrence relation we listed earlier.

The list called listOfFibs has n elements, and each one is a Fibonacci number, starting with the first. Therefore, the last element in the list will be the nth Fibonacci number, and we call this nthFib. This is ultimately the integer that gets returned from the program.

Now, we show a near-identical program for generating the nth Lucas number. There are only two changes compared to the script for Fibonacci numbers. The first such change is purely cosmetic: I’ve replaced the name “listOfFibs” with “listOfLucas” for obvious reasons. The second change is in the base case. Since L_1 = 1 and L_2 = 3, we now need two lines to define these base cases. The first such line returns 1 if n = 1, and the line immediately after returns 3 if n = 2.

Math PhD Student University of Tennessee | Academic Sales Engineer | Writer, Educator, Researcher

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store