The subject of this blog started as a simple coding exercise to illustrate to some of my coworkers one of my early intuition about recursive and iterative algorithms.

Roughly speaking, I will be calling a recursive algorithm to any algorithm that solves a particular problem by calling directly or indirectly to itself. Each call input is smaller or modified version of the initial problem instance. Alternative, a iterative algorithm is an algorithm that solves instances of a problem by a series of steps or iterations. The expectation is that after a number of those steps, the algorithm can output a sound approximation or exact solution for each instance.

Since my teens I had a conjecture, that I would call Bazterra’s conjecture #1¹ without following any particular order.

The relationship between recursive and iterative algorithms is by no means anything new, and it’s currently a well-understood concept. Moreover, there are heuristics rules of when is reasonable to use recursive or iterative algorithm based on the problem instance sizes, and language characteristics used in its implementation².

You can find a simple recursive and iterative versions written in javascript to compute the Fibonacci series in my example GitHub repo. The Fibonacci series is a sequence of numbers defined by the following linear recurrence equation

%% f_n = f_{n-1} + f_{n-2} \text{ for any } n > 1 %%

with initial values \|f_0 = 0\| and \|f_1 = 1\|.

Eventually, I found out that I was not very original when choosing this series for comparing recursive and iterative algorithms that can solve the same problem³. Even more, in the reference [3] the recursive implementation of the Fibonacci is an example of excessive recursion, more about that this in another blog.

From multiple sources I also learned a third way of implementing the series using a closed-form expression or formula for the Fibonacci series⁴. This is basically:

%% f_n = \left[\frac{\varphi^n}{\sqrt{5}}\right] %%

where \|\varphi = \frac{1}{2}\left(1+\sqrt{5}\right)\|, and \|[\cdot]\| denote rounding to the closes integer.

Because I am not formally trained in algorithms, I thought to myself how in the world can this be the Fibonacci series?. Where is the magic that connects Fibonacci recurrence with this formula? Moreover, if you are looking for a more numerological or mystical connection, the constant \|\varphi\| is the famous golden ration⁵.

In my next post, I will try to break this mystical spell by showing that indeed this formula can be used to compute Fibonacci series.

References