Unraveling Recursion Through Classic Problems | CodeSignal Learn

Unraveling Recursion Through Classic Problems | CodeSignal Learn

Skip to main content

Introduction to the Lesson

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 Leonardo of Pisa (also known as Fibonacci), 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.

Problem 1: Fibonacci Sequence

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. Visualizing Fibonacci might be a little bit tricky at first. If you are into art and design, you might have heard about the golden spiral, a logarithmic spiral whose growth factor is linked to the golden ratio . Interestingly, the Fibonacci sequence is connected with the golden ratio as well. If you look at the ratio of two consecutive numbers in the Fibonacci series, you'll observe that it approximates the golden ratio! It's truly fascinating to see such a foundational mathematical pattern connected to art and design.

Problem 1: Naive Recursion Approach

O(2^n)

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Problem 2: Solution Building

Instead of considering the base case as an array with a single element, we modify our approach to use an auxiliary index, index . We initially set it to 0, pointing at the first element in the array. The base case is now when index equals the length of the array. At this point, we have processed all elements in the array, and the function should return 0 as there are no more elements to add. For arrays with more than one element, the function effortlessly adds the current element, pointed at by the index, and the sum of the remaining elements. It achieves this sum by recursively calling the arraySum function, now passing index + 1 as the index. This incremented index moves the 'pointer' to the next element. This way, we can visualize it as moving along the array, adding one element at a time until we reach the end. This index-based approach eliminates the need for slicing the array, making it more space-efficient. With these modifications, our final solution is: def arraySum(arr, index=0): if index == len(arr): return 0 else: return arr[index] + arraySum(arr, index + 1) With this approach, we converge to our sum in a highly efficient and elegant manner without creating unnecessary arrays, ultimately walking our array down to the base case.

Problem 3: Solution Building

As with the other problems, we first tackle the base cases. If n is 0 or 1, the function unflinchingly returns 1. For n greater than 1, the function humbly returns the product of n and the factorial of (n - 1), by calling itself, i.e., the factorial function, recursively acting on (n - 1) . And voila, we have a recursive solution to compute factorials. Here's the recursive function that calculates the factorial of a number: def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n - 1)

Let's look at how memoization can improve our solution:

Python

def fib(n, computed={0: 0, 1: 1}):
    if n not in computed:
        computed[n] = fib(n - 1, computed) + fib(n - 2, computed)
    return computed[n]

In this function, we use a Python dictionary computed to store the Fibonacci numbers we've computed so far. If a number n is not in the dictionary computed, we calculate it using the recursive formula and store the result in our dictionary. If the number n is already in our dictionary, we simply return the value, thus avoiding the computation. Edge cases results (n = 0 and n = 1) are stored in the computed list by default.

This function now computes the nth Fibonacci number in linear time $O(n)$ , which is a significant improvement over the naive recursive implementation. Each number is calculated only once, and the function can handle a large n efficiently.