My DSA Notes 2: Recursion In Python

Introduction:

Recursion is a powerful programming technique that allows a function to call itself to solve a problem. It finds extensive use in various computational tasks and is especially handy when dealing with repetitive calculations.

We will start with simple cases and then increase the complexity as we progress

1. Factorials: The Basics:

Factorial of a non-negative integer n, denoted by n!, is defined as the product of n and all positive integers less than n. For example, 5! is calculated as 5 × 4 × 3 × 2 × 1, resulting in 120.

Understanding the Code:

Let’s explore the Python code snippet for calculating factorials using recursion:

def factorial(n):
    # The Unintentional Case
    if n < 0 or not isinstance(n, int):
        raise ValueError("Input must be a non-negative integer")

    # Base Condition: Exit Condition
    if n in [0, 1]:
        return 1

    # Recursive Case
    return n * factorial(n - 1)

print(factorial(17))

In this code, we have a function called factorial that takes an integer n as input. Here's how it works:

Unintentional Case:

The function begins with input validation to handle the unintentional cases where n is negative or not an integer. It raises a ValueError with a descriptive error message.

Base Condition:

The code then checks for the base condition. If n is either 0 or 1, there's no need for further recursion, so the function returns 1.

Recursive Case:

If the base condition is not met, the function recursively calls itself with the argument n - 1. This step ensures that we calculate the factorial of all the integers from n down to 2. Each recursive call multiplies n by the result of factorial(n - 1), gradually reducing n until it reaches the base condition.

Return the Result:

The final result is obtained by multiplying n with the factorial of n - 1. The recursion continues until the base condition is reached, and the final calculated value is returned.

2. Understanding Fibonacci Numbers:

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones. It starts with 0 and 1, so the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

Exploring the Code:

Let’s dive into the Python code snippet for calculating Fibonacci numbers using recursion:

def fibonacci(n, previous_list={}):
    # Unintentional Case
    if n < 0 or not isinstance(n, int):
        raise ValueError("Input must be a positive integer")

    # Base Conditions
    if n in previous_list:
        return previous_list[n]
    if n == 0:
        return 0
    if n in [1, 2]:
        return 1

    # Recursive Conditions
    previous_list[n] = fibonacci(n - 1, previous_list) + fibonacci(n - 2, previous_list)
    return previous_list[n]

for i in range(10):
    print(f"{i} -> {fibonacci(i)}")

The code implements the Fibonacci sequence calculation using recursion. Here’s a breakdown of its functionality:

Unintentional Case:

The code begins with input validation to handle unintentional cases where n is negative or not an integer. It raises a ValueError with an appropriate error message.

Base Conditions:

The code checks for three base conditions:

• If n is already present in the previous_list dictionary, it means that the Fibonacci number for n has already been calculated. In this case, the function retrieves the pre-calculated value and returns it.
• If n is 0, the function returns 0 since the Fibonacci sequence starts with 0.
• If n is 1 or 2, the function returns 1 since these are the first two numbers in the Fibonacci sequence.

Recursive Conditions:

If none of the base conditions are met, the function recursively calls itself twice to calculate the Fibonacci numbers for n-1 and n-2, respectively. These recursive calls continue until the base conditions are reached. The calculated values are then stored in the previous_list dictionary to avoid redundant calculations.

Return the Result:

The final result is obtained by summing the Fibonacci numbers for n-1 and n-2. The result is stored in the previous_list dictionary for future reference and returned.

Printing Fibonacci Numbers:

To demonstrate the functionality, the code includes a loop that iterates through the numbers from 0 to 9. For each number i, it calls the fibonacci function and prints the value of the Fibonacci number for that index.

3. Recursive Magic: Summing Digits with Python

The task at hand is to calculate the sum of the individual digits in a positive integer. For example, given the number 123, the sum of its digits would be 1 + 2 + 3 = 6.

Deconstructing the Code:

Let’s delve into the Python code snippet for summing the digits of a positive integer using recursion:

def sum_of_digits(number):
    # Unintentional Case
    if number < 0 or not isinstance(number, int):
        raise ValueError("Input must be a positive integer")

    # Base Condition
    if number < 10:
        return number

    # Recursive Condition
    last_digit = number - ((number // 10) * 10)
    rest_of_digits = (number // 10)
    return last_digit + sum_of_digits(rest_of_digits)

print(sum_of_digits(101010))

The code employs recursion to calculate the sum of the digits in a positive integer. Here’s a breakdown of its functionality:

Unintentional Case:

The code begins with input validation to handle unintentional cases where number is negative or not an integer. It raises a ValueError with an appropriate error message.

Base Condition:

The code checks if number is less than 10. If true, it means that number consists of only one digit, and the function returns the value of number itself.

Recursive Condition:

If number has more than one digit, the function extracts the last digit using modulo 10 (last_digit) and the remaining digits by performing an integer division by 10 (rest_of_digits). It then recursively calls itself, passing rest_of_digits as the new argument. This recursive call continues until the base condition is met.

Return the Result:

The final result is obtained by summing the last digit (last_digit) with the sum of the digits in rest_of_digits, which is calculated by the recursive call to sum_of_digits(rest_of_digits).

Printing the Result:

To showcase the functionality, the code includes a print statement that calls the sum_of_digits function with the number 101010 and prints the result.

4. Empowering Algorithms: Harnessing the Power of Recursion for Exponentiation

Understanding Exponentiation:

Exponentiation refers to the process of raising a number to a certain power. For example, 3⁴ means raising the number 3 to the power of 4, resulting in 81.

Unraveling the Code:

Let’s dive into the Python code snippet that calculates the power of a number using recursion:

def power_of_x(x, y):
    # Unintentional Case
    if type(x) not in [int, float] or not isinstance(y, int) or y < 0:
        raise ValueError("X must be an integer and Y must be a positive integer")

    # Base Conditions
    if y == 0:
        return 1
    if y == 1:
        return x

    # Recursive Condition
    return x * power_of_x(x, y - 1)

print(power_of_x(3, 4))

The code utilizes recursion to calculate the power of a number. Here’s a breakdown of its functionality:

Unintentional Case:

The code begins with input validation to handle unintentional cases where x is not an integer or float, y is not an integer, or y is a negative number. It raises a ValueError with an appropriate error message.

Base Conditions:

The code checks for two base conditions:

• If y is 0, the function returns 1 since any number raised to the power of 0 is 1.
• If y is 1, the function returns x itself since any number raised to the power of 1 is the number itself.

Recursive Condition:

If neither of the base conditions is met, the function recursively calls itself, multiplying x with the result of power_of_x(x, y - 1). This recursive call continues until the base conditions are reached.

Return the Result:

The final result is obtained by multiplying x with the value returned by the recursive call to power_of_x(x, y - 1). This represents the power of x raised to the power of y.

Printing the Result:

To showcase the functionality, the code includes a print statement that calls the power_of_x function with x as 3 and y as 4, and prints the result.

5. Uncovering Common Divisors: Exploring Recursive GCF Calculation

Introduction:

Recursion, a powerful programming technique, enables developers to solve complex problems by breaking them down into simpler, more manageable subproblems. Now, we’ll explore the fifth example from the provided code snippets, which demonstrates the use of recursion to find the greatest common factor (GCF) or divisor of two integers using the Euclidean Algorithm in Python.

Understanding the Greatest Common Factor:

The greatest common factor (GCF) or greatest common divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCF of 24 and 36 is 12.

Unraveling the Code:

Let’s dive into the Python code snippet that calculates the GCF of two numbers using recursion:

def gcf(x, y):
    # Unintentional Case
    if isinstance(x, int) and isinstance(y, int):
        if x < 0:
            x = x * -1
        if y < 0:
            y = y * -1
    else:
        raise ValueError("Input has to be integers")

    # Base Condition
    if y == 0:
        return x

    # Recursive Case
    return gcf(y, x % y)

print(gcf(985602920, -1448))

The code employs recursion to calculate the GCF of two numbers. Here’s a breakdown of its functionality:

Unintentional Case:

The code includes input validation to handle unintentional cases. It checks if x and y are integers. If they are, it ensures that both values are positive by converting negative values to positive. If either of the inputs is not an integer, it raises a ValueError with an appropriate error message.

Base Condition:

The code checks if y is 0. If true, it means that x is the GCF, and the function returns the value of x.

Recursive Case:

If y is not 0, the function recursively calls itself, passing y as the new value of x and x % y as the new value of y. This step utilizes the Euclidean Algorithm, which replaces x with y and y with the remainder of x divided by y. The recursive calls continue until the base condition is met.

Return the Result:

The final result is obtained when the recursive calls reach the base condition, returning the GCF of the original values of x and y.

Printing the Result:

To showcase the functionality, the code includes a print statement that calls the gcf function with x as 985602920 and y as -1448, and prints the result.

6. Binary Conversions Unveiled: Recursive Decimal to Binary Conversion

Introduction:

Now, we’ll explore the sixth example from the provided code snippets, which showcases the use of recursion to convert decimal numbers to binary representation in Python.

Understanding Decimal to Binary Conversion:

Decimal to binary conversion involves converting a base-10 (decimal) number to its equivalent representation in base-2 (binary). The binary number system uses only two digits, 0 and 1, to represent all numbers. For example, converting the decimal number 10 to binary results in the binary representation 1010.

Unraveling the Code:

Let’s dive into the Python code snippet that converts decimal numbers to binary using recursion:

def dec_to_bin(d):
    # Exception Case
    if d < 0 or not isinstance(d, int):
        raise ValueError("Please input positive integers only")

    # Base Cases
    if d == 0:
        return "0"
    if d == 1:
        return "1"

    # Recursive Case
    reminder = d % 2
    quotient = d // 2
    return dec_to_bin(quotient) + str(reminder)

print(dec_to_bin(1000))

The code utilizes recursion to convert decimal numbers to binary representation. Here’s a breakdown of its functionality:

Exception Case:

The code includes input validation to handle exception cases. It checks if d is a positive integer. If d is negative or not an integer, it raises a ValueError with an appropriate error message.

Base Cases:

The code checks for two base cases:

• If d is 0, the function returns "0" since 0 in decimal is represented as "0" in binary.
• If d is 1, the function returns "1" since 1 in decimal is represented as "1" in binary.

Recursive Case:

If neither of the base cases is met, the function recursively calls itself. It calculates the remainder (reminder) when d is divided by 2 and the quotient (quotient) when d is divided by 2 using integer division (//). The recursive call is made with the quotient as the new value of d. The binary representation is obtained by concatenating the result of the recursive call (dec_to_bin(quotient)) with the string representation of the remainder (str(reminder)).

Return the Result:

The final result is obtained when the recursive calls reach the base cases and return the binary representation of the original decimal number.

Printing the Result:

To showcase the functionality, the code includes a print statement that calls the dec_to_bin function with d as 1000 and prints the resulting binary representation.

7. Binary to Decimal: Unraveling Recursive Conversion

Let’s explore the seventh example from the provided code snippets, which showcases the use of recursion to convert binary numbers to their decimal representation in Python.

Understanding Binary to Decimal Conversion:

Binary to decimal conversion involves converting a base-2 (binary) number to its equivalent representation in base-10 (decimal). The decimal number system uses ten digits, from 0 to 9, to represent all numbers. For example, converting the binary number 1010 to decimal results in the decimal representation 10.

Unraveling the Code:

Let’s dive into the Python code snippet that converts binary numbers to decimal using recursion:

def bin_to_dec(b, i=0):
    # Exception Case
    if not isinstance(b, str):
        raise ValueError("Please input a string of 0s and 1s only")

    # Base Case
    if len(b) == 0:
        return 0

    # Recursive Case
    return bin_to_dec(b[:-1], i + 1) + int(b[-1]) * pow(2, i)

print(bin_to_dec("101010101"))

The code utilizes recursion to convert binary numbers to their decimal representation. Here’s a breakdown of its functionality:

Exception Case:

The code includes input validation to handle exception cases. It checks if b is a string containing only 0s and 1s. If b is not a string or contains characters other than 0 and 1, it raises a ValueError with an appropriate error message.

Base Case:

The code checks for a base case: if the length of the binary string b is 0, it means there are no more digits to process, and the function returns 0.

Recursive Case:

If the base case is not met, the function recursively calls itself. It calculates the decimal value of the binary number by summing two components:

• The recursive call bin_to_dec(b[:-1], i + 1) processes the binary number without the last digit (b[:-1]) and increments the power of 2 (i + 1).
• The product of the last digit of the binary number (int(b[-1])) and the power of 2 (pow(2, i)) accounts for the value of the current digit.

Return the Result:

The final result is obtained when the recursive calls reach the base case, and the decimal values are calculated and summed.

Printing the Result:

To showcase the functionality, the code includes a print statement that calls the bin_to_dec function with the binary string "101010101" and prints the resulting decimal representation.

8. Embracing Recursion: Exploring Nested Even Sum

Let us delve into the eighth example from the provided code snippets, which demonstrates the use of recursion to calculate the sum of all even numbers within a nested object in Python.

Understanding Nested Even Sum:

Nested even sum involves calculating the sum of all even numbers within an object that may contain nested objects. The task requires traversing the object and its nested structures, identifying even numbers, and summing them. This recursive approach allows us to handle complex nested objects with varying levels of depth.

Unraveling the Code:

Let’s examine the Python code snippet that implements the nested even sum using recursion:

def nested_even_sum(obj):
    # Base Condition
    if not obj:
        return 0

    # Recursive Condition
    sum = 0

    k, v = obj.popitem()
    if isinstance(v, int):
        if v % 2 == 0:
            sum += v
    elif isinstance(v, dict):
        sum += nested_even_sum(v)

    return sum + nested_even_sum(obj)


obj1 = {
    "outer": 2,
    "obj": {
        "inner": 2,
        "otherObj": {
            "superInner": 2,
            "notANumber": True,
            "alsoNotANumber": "yup"
        }
    }
}

obj2 = {
    "a": 2,
    "b": {"b": 2, "bb": {"b": 3, "bb": {"b": 2}}},
    "c": {"c": {"c": 2}, "cc": 'ball', "ccc": 5},
    "d": 1,
    "e": {"e": {"e": 2}, "ee": 'car'}
}

print(nested_even_sum(obj1))  # 6
print(nested_even_sum(obj2))  # 10

The code snippet showcases the recursive approach to calculate the sum of even numbers within a nested object. Let’s understand its functionality:

Base Condition:

The code checks for a base condition to stop the recursion. If the object (obj) is empty or evaluates to False, the function returns 0. This serves as the termination condition for the recursion.

Recursive Condition:

If the base condition is not met, the function continues the recursion to explore the object and its nested structures. It initializes a variable sum to store the sum of even numbers found.

Traversing the Object:

The code uses the popitem() method to retrieve and remove the last key-value pair from the object (obj). The key is stored in k, and the value is stored in v.

Checking for Even Numbers:

The code checks if the value (v) is an integer. If it is, it further checks if the value is even (v % 2 == 0). If it is even, it adds the value to the sum.

Handling Nested Objects:

If the value (v) is a dictionary (nested object), the code recursively calls the nested_even_sum function with the nested object (v) as the input. The result of the recursive call is added to the sum.

Return the Result:

The final result is obtained by summing the current sum and the result of the recursive calls. This accounts for the even numbers found within the current object and all its nested structures.

Testing the Code:

The code includes two test cases (obj1 and obj2) to demonstrate the functionality. The nested_even_sum function is called with these objects as input, and the results are printed. In the given examples, obj1 yields a sum of 6, while obj2 yields a sum of 10.

9. Stringify Numbers: Recursively Converting Numeric Values to Strings

We’ll now explore the ninth example from the provided code snippets, which showcases the use of recursion to convert numeric values within a nested object to their string representations in Python.

Understanding Numeric Stringification:

Stringifying numbers involves converting numeric values within an object to their string representations. This is particularly useful when dealing with nested objects that contain numerical data. By recursively traversing the object and its nested structures, we can convert all numeric values to strings, preserving the overall structure of the object.

Unraveling the Code:

Let’s examine the Python code snippet that implements the conversion of numeric values to strings using recursion:

def stringifyNumbers(obj):
    # Recursive Condition
    for k in obj:
        if isinstance(obj[k], int):
            obj[k] = str(obj[k])
        elif isinstance(obj[k], dict):
            obj[k] = stringifyNumbers(obj[k])

    return obj

obj = {
    "num": 1,
    "test": [],
    "data": {
        "val": 4,
        "info": {
            "isRight": True,
            "random": 66
        }
    }
}

print(obj)
print(stringifyNumbers(obj))

The code snippet demonstrates the recursive approach to convert numeric values to strings within a nested object. Let’s understand its functionality:

Recursive Condition:

The stringifyNumbers function takes an object (obj) as input. It iterates over each key (k) in the object.

Checking Numeric Values:

For each key, the code checks if the corresponding value (obj[k]) is an integer using the isinstance() function. If it is, the value is converted to a string using the str() function and reassigned to the same key within the object.

Handling Nested Objects:

If the value is a dictionary (nested object), the code recursively calls the stringifyNumbers function with the nested object as the input (obj[k] = stringifyNumbers(obj[k])). This ensures that all levels of nested objects are processed and converted.

Returning the Result:

After iterating through all keys in the object and processing their values, the modified object with stringified numbers is returned.

Testing the Code:

The code includes a test case where an object (obj) is defined with numeric values at various levels of nesting. The original object is printed, and then the stringifyNumbers function is called on the object, resulting in the conversion of numeric values to strings. The modified object is printed again to showcase the conversion.

Conclusion:

In this series of articles, we explored several examples that showcased the power and versatility of recursion in solving various programming problems. Recursion, a fundamental concept in computer science and programming, allows us to break down complex problems into simpler subproblems and solve them in an elegant and efficient manner.

Throughout the articles, we covered different aspects of recursion, ranging from calculating factorials and Fibonacci numbers to performing mathematical operations and manipulating nested objects. Each example demonstrated how recursion can simplify problem-solving by utilizing base conditions and recursive calls.

Recursion offers several advantages. It enables us to write concise and expressive code by leveraging the repetitive nature of certain algorithms. It allows us to tackle complex problems by breaking them down into smaller, more manageable tasks. Additionally, recursion can provide an elegant solution for working with hierarchical or nested data structures.

However, recursion also comes with potential challenges. If not implemented correctly, it can lead to infinite loops and excessive memory usage. Therefore, it is essential to define appropriate base conditions and ensure that recursive calls converge towards termination. Understanding the concept of recursion and practicing its implementation is crucial for harnessing its power effectively.

By studying and experimenting with the provided code snippets, we gained insights into how recursion can be applied to various problem domains. From mathematical calculations to data manipulation, recursion proved to be a valuable tool in our programming toolkit.

As you continue your journey in programming, it is important to explore further examples, practice writing recursive functions, and deepen your understanding of recursion’s principles and best practices. With time and experience, you will develop a strong intuition for when and how to apply recursion effectively.

Remember that recursion is just one of many problem-solving techniques available to programmers. Combining it with other concepts and algorithms will enable you to tackle even more complex challenges and enhance your overall programming skills.

Level Up Coding

Thanks for being a part of our community! Before you go:

• 👏 Clap for the story and follow the author 👉
• 📰 View more content in the Level Up Coding publication
• 💰 Free coding interview course ⇒ View Course
• 🔔 Follow us: Twitter | LinkedIn | Newsletter

🚀👉 Join the Level Up talent collective and find an amazing job