Member-only story
Fibonacci and Lucas Formulas in Python
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…