Welcome to our hands-on lesson in which we explore the fascinating concept of recursion on practice. Throughout this lesson, we'll peel back the layers of three foundational problems - Generating the Fibonacci sequence, Finding the sum of all elements in an array, and Calculating factorials. We'll systematically deconstruct each of these problems, expose the core of each solution, and then rebuild them. If the name Fibonacci reminds you of Fibonacci de Piso, one of the most famous mathematicians of the Middle Ages renowned for his work on the Fibonacci sequence, you're not mistaken. Buckle up as we'll retrace this journey of Fibonacci.
So, what is the Fibonacci sequence? The Fibonacci sequence is an infinite sequence of numbers, starting with 0 and 1, with every subsequent number being the sum of the previous two numbers: 0
, 1
, 1
, 2
, 3
, 5
, 8
, 13
, ...
Given a number n
, our task is to implement a recursive algorithm that returns the n
-th number in the Fibonacci sequence. Remember, indexing starts from 0, just like Python's 0-index style.
