Recursion

Recursion

Recursion is a useful tool to solve certain types of problems. The use case here is to help us arrive at a dynamic programming solution. A recursive function is a function that calls itself until it hits a stopping condition or what we sometimes call the base case.

I will use four examples hands-on to express the concept of recursion and why you should master it. These include:

• Count Down
• Fibonacci Sequence
• File Search
• Factorials

Count Down

class Solution:
    
    def count_down_timer(self, n):
        """
        Prints a countdown from n to 1 recursively.

        Parameters:
        - n (int): The starting number for the countdown.

        Returns:
        - None
        """
        # Base case: Stop the recursion when n is less than 1
        if n < 1:
            return
        
        # Print the current value of n
        print(n)

        # Recursively call count_down_timer with the next value (n-1)
        return self.count_down_timer(n-1)

# Create an instance of the Solution class
sol = Solution()

# Start the countdown from 10
sol.count_down_timer(10)

Fibonacci Sequence

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on, where each number (after the first two) is the sum of the two preceding ones.

The recursive formula for the Fibonacci sequence is often expressed as:

F(n)=F(n−1)+F(n−2)

with base cases F(0)=0 and F(1)=1

Wondering how you can apply Fibonacci in real life? Here's the drill!

Financial Applications

Fibonacci numbers and ratios are used in financial analysis, particularly in technical analysis of stock markets. Traders use Fibonacci retracement levels to identify potential reversal levels in stock prices.

Art and Design

Artists and designers sometimes use Fibonacci numbers and the golden ratio derived from them to create aesthetically pleasing compositions in art and architecture.

Mathematical Models

Fibonacci numbers appear in various mathematical models, including number theory, combinatorics, and algebra.

class Solution:

    def fib(self, n):
        """
        Calculate the nth Fibonacci number using recursion.

        Parameters:
        - n (int): The index of the Fibonacci number to be calculated.

        Returns:
        - int: The nth Fibonacci number.
        """
        # Base cases: Fibonacci of 0 is 0, and Fibonacci of 1 is 1
        if n == 0:
            return 0
        if n == 1:
            return 1

        # Recursive calculation: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
        return self.fib(n - 1) + self.fib(n - 2)

# Create an instance of the Solution class
sol = Solution()

# Calculate and print the 10th Fibonacci number
print("fib(10):", sol.fib(10))

File Search

Recursion comes in handy when the recursive algorithm is simpler to write than using the non-recursive approach.

The utility function will continue searching in all the subfolders of each sub-folder until it completes the full search or finds the file that you're looking for. It returns results to the user when it finds it or runs out of folders to search for.

Non-Recursive Implementation

We start by putting the starting directory in the buffer right in the memory.  For example, if we want to look for it in a directory called personal_documents, we put that directory in a buffer.

Then we read it from this memory location(buffer)

We then search for all the files in that particular directory and if it is found, we just output the file.

If it's not found, we store all the sub-directories in that same buffer and go back to the step where we read one of the directories from the buffer and do this step over and over again in the given buffer. However, note that the buffer must not be empty.

Recursive Approach

Now, we want to do a comparison between the previous non-recursive approach versus the recursive approach.

- Here, we first search the starting directory for the file that we're looking for.

- If we find the file, we output it.

- However, if we don't find it for every sub-directory that we have, we do a recursive call into the same function.

- This approach is a lot simpler than the complex non-recursive approach.

import os
from os.path import isfile, join

class Solution:
    
    def search(self, full_filepath, filename):
        """
        Recursively search for a file in a directory and its subdirectories.

        Parameters:
        - full_filepath (str): The path to the current directory or file being checked.
        - filename (str): The name of the file to search for.

        Returns:
        - bool: True if the file is found, False otherwise.
        """
        # Print the path being checked
        print("Checking: " + full_filepath)

        # Check if the filename is present in the current path
        if filename in full_filepath:
            print("Found " + filename + " in " + full_filepath)
            return True

        # If it's a file, return False (end of recursion for this branch)
        if isfile(full_filepath):
            return False

        # Iterate over files in the current directory and recursively search
        for file in os.listdir(full_filepath):
            found = self.search(join(full_filepath, file), filename)
            if found:
                return True

# Create an instance of the Solution class
sol = Solution()

# Search for the file "table.pdf" in the "~/Downloads" directory
sol.search("~/Downloads", "table.pdf")

Factorials

A factorial function is a mathematical function responsible for calculating the product of all positive integers up to a given positive integer n. It is denoted by n! and is defined as:

The factorial function is commonly used in mathematics and has various applications in combinatorics, probability theory, and calculus. In programming, the factorial function is often implemented to calculate the factorial of a non-negative integer.

Factorials are frequently used in counting problems, probability calculations, and mathematical expressions involving permutations and combinations.

class Solution:
    
    def factorial(self, n):
        """
        Calculate the factorial of a non-negative integer using recursion.

        Parameters:
        - n (int): The non-negative integer for which to calculate the factorial.

        Returns:
        - int: The factorial of the given integer.
        """
        # Base case: Factorial of 0 or negative numbers is 1
        if n < 1:
            return 1

        # Recursive calculation: n! = n * (n-1)!
        return n * self.factorial(n - 1)

# Create an instance of the Solution class
sol = Solution()

# Calculate and print the factorial of 5
print("factorial(5):", sol.factorial(5))

Time Complexity

The time complexity of the factorial function is O(n) due to its recursive nature. In each recursive call, the function performs a constant amount of work (multiplication and subtraction) until it reaches the base case where n becomes less than 1.

The number of recursive calls made is directly proportional to the value of n, making the time complexity linear.

Space Complexity

The space complexity is also O(n) due to the recursive calls that are stored on the call stack. In the worst case, the maximum depth of the call stack is equal to n when n is the largest value in the recursive chain.

Each recursive call adds a new frame to the call stack.

It's worth noting that while the recursive approach is elegant, it may not be the most efficient for very large values of n due to the risk of stack overflow. As a result, I recommend you consider, iterative solutions or memoization techniques for optimizing the function for large inputs.