The Recamán’s Sequence (Recursive Algorithm)

The Recamán’s Sequence is a well-known recursive sequence used in Mathematics and Computer Science. It can easily be implemented using a recursive function.

Recamán’s sequence a₀, a₁, a₂, … is defined as:

The first terms of the sequence are:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42, 17, 43, 16, 44, 15, 45, 14, 46, 79, 113, 78, 114, 77, 39, 78, 38, 79, 37, 80, 36, 81, 35, 82, 34, 83, 33, 84, 32, 85, 31, 86, 30, 87, 29, 88, 28, 89, 27, 90, 26, 91, 157, 224, 156, 225, 155, …

By drawing an arc between each consecutive number of the Recamán’s Sequence we can create beautiful visual representations of the sequence:

The above visualisation represents the first 70 numbers of the Recamán’s Sequence
To create this visual representation, we start with a₀=0 and then draw an arc between each consecutive set of values of the sequence:

Recursive Function

Let’s implement a recursive function in Python to generate the first n values of the Recamán’s sequence: