PYTHON RECURSION

Solve complex algorithmic problems by writing functions that call themselves recursively in Python.

🔄 What is Recursion in Python?

Recursion is a programming technique where a function calls itself to solve a smaller instance of the same problem. Every recursive function requires two core components: 1. Base Case: The stopping condition that terminates recursion to prevent infinite loops. 2. Recursive Step: The process where the function calls itself with modified parameters moving closer to the base case.

1. Basic Recursion Anatomy (Countdown Timer)
A simple recursive function that counts down from a given number to zero.
Python
def recursive_countdown(n):
    # Base Case: stop when n reaches 0
    if n <= 0:
        print("Liftoff! 🚀")
        return
    
    print(f"Countdown: {n}")
    # Recursive Step: call function with n - 1
    recursive_countdown(n - 1)

recursive_countdown(3)
Output: Countdown: 3 Countdown: 2 Countdown: 1 Liftoff! 🚀
Real-Time Example 1: Mathematical Factorial Calculation
Calculate the factorial of a number ($n!$) using recursive multiplication.
Python
def calculate_factorial(n):
    # Base Case
    if n == 0 or n == 1:
        return 1
    
    # Recursive Step
    return n * calculate_factorial(n - 1)

print("Factorial of 5 (5!):", calculate_factorial(5))
Output: Factorial of 5 (5!): 120
Real-Time Example 2: Fibonacci Sequence Generator
Compute the $n$-th number in the Fibonacci sequence where each number is the sum of the two preceding ones.
Python
def fibonacci(n):
    # Base Cases
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    
    # Recursive Step
    return fibonacci(n - 1) + fibonacci(n - 2)

# Generate first 6 Fibonacci numbers
fib_series = [fibonacci(i) for i in range(6)]
print("Fibonacci Series:", fib_series)
Output: Fibonacci Series: [0, 1, 1, 2, 3, 5]
Real-Time Example 3: Summing Elements in a Nested List
Recursively traverse and calculate the sum of numbers stored in multi-dimensional nested lists.
Python
def recursive_sum(nested_list):
    total = 0
    for element in nested_list:
        if isinstance(element, list):
            total += recursive_sum(element)  # Recursive call for nested sublist
        else:
            total += element
    return total

complex_data = [10, [20, 30], [40, [50, 60]]]
print("Total Sum of Nested List:", recursive_sum(complex_data))
Output: Total Sum of Nested List: 210
Real-Time Example 4: Calculating Power Exponents ($x^y$)
Compute the power of a base number raised to an exponent using recursion.
Python
def power(base, exponent):
    # Base Case
    if exponent == 0:
        return 1
    
    # Recursive Step
    return base * power(base, exponent - 1)

print("2 raised to power 4 (2^4):", power(2, 4))
Output: 2 raised to power 4 (2^4): 16
Real-Time Example 5: Palindrome String Checker
Verify whether a word reads the same forwards and backwards using recursive character comparisons.
Python
def is_palindrome(word):
    # Base Cases
    if len(word) <= 1:
        return True
    
    if word[0] != word[-1]:
        return False
    
    # Recursive Step: test substring excluding first and last character
    return is_palindrome(word[1:-1])

print("Is 'radar' a palindrome?", is_palindrome("radar"))
print("Is 'python' a palindrome?", is_palindrome("python"))
Output: Is 'radar' a palindrome? True Is 'python' a palindrome? False
Real-Time Example 6: Binary Search (Recursive Algorithm)
Locate the index of a target element in a sorted list efficiently using recursive binary search.
Python
def binary_search(arr, target, low, high):
    if low > high:
        return -1  # Base Case: Element not found
    
    mid = (low + high) // 2
    
    if arr[mid] == target:
        return mid  # Base Case: Element found at index mid
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, high)

sorted_numbers = [10, 20, 35, 50, 75, 90]
target_val = 75
result_index = binary_search(sorted_numbers, target_val, 0, len(sorted_numbers) - 1)

print(f"Target {target_val} found at index:", result_index)
Output: Target 75 found at index: 4
Real-Time Example 7: JSON Tree Traversal / Key Lookup
Search for a specific key recursively across hierarchical nested dictionary (JSON) structures.
Python
def find_key_in_json(data, target_key):
    if target_key in data:
        return data[target_key]
    
    for key, value in data.items():
        if isinstance(value, dict):
            result = find_key_in_json(value, target_key)
            if result is not None:
                return result
    return None

nested_json = {
    "user": {
        "id": 101,
        "profile": {
            "username": "nikita_dev",
            "email": "nikita@infotech.com"
        }
    }
}

print("Found Email:", find_key_in_json(nested_json, "email"))
Output: Found Email: nikita@infotech.com
Real-Time Example 8: Greatest Common Divisor (Euclidean Algorithm)
Find the Greatest Common Divisor (GCD) of two numbers recursively.
Python
def gcd(a, b):
    # Base Case
    if b == 0:
        return a
    
    # Recursive Step
    return gcd(b, a % b)

print("GCD of 48 and 18:", gcd(48, 18))
Output: GCD of 48 and 18: 6
Real-Time Example 9: String Reversal
Reverse a string characters recursively by moving the first character to the end.
Python
def reverse_string(s):
    # Base Case
    if len(s) == 0:
        return s
    
    # Recursive Step
    return reverse_string(s[1:]) + s[0]

print("Reversed 'Python':", reverse_string("Python"))
Output: Reversed 'Python': nohtyP