Recursion in Python - Deep Dive into Recursive Functions

Recursion is a programming technique where a function calls itself directly or indirectly. It is extremely useful in solving divide-and-conquer problems, tree/graph traversals, combinatorics, and dynamic programming. Let’s explore it in detail.

🔎 Key Concepts of Recursion

✅ 1. Base Case

The condition under which the recursion ends. Without it, recursion continues infinitely, leading to a stack overflow.

✅ 2. Recursive Case

The part of the function where the function calls itself with simplified input, moving closer to the base case.

ℹ️ Tips for Writing Recursive Functions

Identify the Base Case: Define the condition that stops recursion.
Ensure Progress: Each call should reduce the problem.
Visualize the Call Stack: Helps debug and understand the flow.
Avoid Redundant Work: Use memoization or switch to iteration.
Trace Small Inputs: Great for learning and debugging.

🎓 General Structure

def recursive_function(parameters):
    if base_case_condition:
        return base_case_value
    else:
        # process and recursive call
        return recursive_function(modified_parameters)

✨ Classic Recursive Examples

1. ⚛️ Factorial

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Use Case: Mathematics, permutations, combinations.

2. 🌐 Fibonacci Sequence

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))  # Output: 13

Warning: Exponential time. Use lru_cache or DP.

3. ➕ Sum of List

def sum_list(lst):
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4]))  # Output: 10

Use Case: Simplifying aggregation.

4. 💾 Generate Permutations

def permutations(s):
    if len(s) == 1:
        return [s]
    perms = []
    for i in range(len(s)):
        for p in permutations(s[:i] + s[i+1:]):
            perms.append(s[i] + p)
    return perms

print(permutations("abc"))  # Output: ['abc', 'acb', ...]

Use Case: Combinatorics, backtracking problems.

This function uses recursion to generate all permutations. The base case handles the simplest scenario where the string length is 1, returning the string itself in a list. For longer strings, it iterates through each character, removes it from the string, and recursively generates permutations of the remaining characters. These partial permutations are then combined with the removed character to form the full permutations.

Explanation:

Base Case: When the length of the string is 1, return a list containing just that string.
Recursive Case: For each character in the string, remove the character and recursively find permutations of the remaining substring. Prepend the removed character to each of these permutations and add them to the list of permutations.

Let’s break down the execution of the recursive permutations function step by step using the input "abc".

Step-by-Step Execution

Initial Call: permutations("abc")
- The input string is "abc", which is longer than 1 character.
- Initialize perms as an empty list: perms = [].
First Level of Recursion:
- Loop over each character in "abc":
  - For i = 0 (character 'a'):
    - Remove 'a', remaining string: "bc".
    - Recursive call: permutations("bc").
Second Level of Recursion: permutations("bc")
- The input string is "bc", which is longer than 1 character.
- Initialize perms as an empty list: perms = [].
Second Level: Loop over "bc":
- For i = 0 (character 'b'):
  - Remove 'b', remaining string: "c".
  - Recursive call: permutations("c").
Third Level of Recursion: permutations("c")
- The input string is "c", which has only 1 character.
- Base case: return ["c"].
Back to Second Level: Continue with "bc":
- For i = 0 (character 'b'):
  - Combine 'b' with permutations of "c": 'b' + "c" = "bc".
  - Add to perms: perms = ["bc"].
- For i = 1 (character 'c'):
  - Remove 'c', remaining string: "b".
  - Recursive call: permutations("b").
Third Level of Recursion: permutations("b")
- The input string is "b", which has only 1 character.
- Base case: return ["b"].
Back to Second Level: Continue with "bc":
- For i = 1 (character 'c'):
  - Combine 'c' with permutations of "b": 'c' + "b" = "cb".
  - Add to perms: perms = ["bc", "cb"].
- Return ["bc", "cb"] to the first level call.
Back to First Level: Continue with "abc":
- For i = 0 (character 'a'):
  - Combine 'a' with permutations of "bc":
    - 'a' + "bc" = "abc".
    - 'a' + "cb" = "acb".
  - Add to perms: perms = ["abc", "acb"].
- For i = 1 (character 'b'):
  - Remove 'b', remaining string: "ac".
  - Recursive call: permutations("ac").
Second Level of Recursion: permutations("ac")
- The input string is "ac", which is longer than 1 character.
- Initialize perms as an empty list: perms = [].
Second Level: Loop over "ac":
- For i = 0 (character 'a'):
  - Remove 'a', remaining string: "c".
  - Recursive call: permutations("c").
Third Level of Recursion: permutations("c")
- The input string is "c", which has only 1 character.
- Base case: return ["c"].
Back to Second Level: Continue with "ac":
- For i = 0 (character 'a'):
  - Combine 'a' with permutations of "c": 'a' + "c" = "ac".
  - Add to perms: perms = ["ac"].
- For i = 1 (character 'c'):
  - Remove 'c', remaining string: "a".
  - Recursive call: permutations("a").
Third Level of Recursion: permutations("a")
- The input string is "a", which has only 1 character.
- Base case: return ["a"].
Back to Second Level: Continue with "ac":
- For i = 1 (character 'c'):
  - Combine 'c' with permutations of "a": 'c' + "a" = "ca".
  - Add to perms: perms = ["ac", "ca"].
- Return ["ac", "ca"] to the first level call.
Back to First Level: Continue with "abc":
- For i = 1 (character 'b'):
  - Combine 'b' with permutations of "ac":
    - 'b' + "ac" = "bac".
    - 'b' + "ca" = "bca".
  - Add to perms: perms = ["abc", "acb", "bac", "bca"].
- For i = 2 (character 'c'):
  - Remove 'c', remaining string: "ab".
  - Recursive call: permutations("ab").
Second Level of Recursion: permutations("ab")
- The input string is "ab", which is longer than 1 character.
- Initialize perms as an empty list: perms = [].
Second Level: Loop over "ab":
- For i = 0 (character 'a'):
  - Remove 'a', remaining string: "b".
  - Recursive call: permutations("b").
Third Level of Recursion: permutations("b")
- The input string is "b", which has only 1 character.
- Base case: return ["b"].
Back to Second Level: Continue with "ab":
- For i = 0 (character 'a'):
  - Combine 'a' with permutations of "b": 'a' + "b" = "ab".
  - Add to perms: perms = ["ab"].
- For i = 1 (character 'b'):
  - Remove 'b', remaining string: "a".
  - Recursive call: permutations("a").
Third Level of Recursion: permutations("a")
- The input string is "a", which has only 1 character.
- Base case: return ["a"].
Back to Second Level: Continue with "ab":
- For i = 1 (character 'b'):
  - Combine 'b' with permutations of "a": 'b' + "a" = "ba".
  - Add to perms: perms = ["ab", "ba"].
- Return ["ab", "ba"] to the first level call.
Back to First Level: Continue with "abc":
- For i = 2 (character 'c'):
  - Combine 'c' with permutations of "ab":
    - 'c' + "ab" = "cab".
    - 'c' + "ba" = "cba".
  - Add to perms: perms = ["abc", "acb", "bac", "bca", "cab", "cba"].
Final Result:
- Return the final list of permutations: ["abc", "acb", "bac", "bca", "cab", "cba"].

🏆 Advanced Examples

1. 🔎 Recursive Binary Search

def binary_search(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    return binary_search(arr, target, low, mid - 1)

print(binary_search([1, 3, 5, 7, 9], 7, 0, 4))  # Output: 3

Use Case: Search in sorted lists, efficient lookups.

2. 🏠 Tower of Hanoi

def tower_of_hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    tower_of_hanoi(n-1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    tower_of_hanoi(n-1, auxiliary, target, source)

tower_of_hanoi(3, 'A', 'C', 'B')

Use Case: Classic recursion problem, understanding state transitions.

🧪 Recursive Problem Types

Problem Type	Examples
Divide & Conquer	Merge Sort, Quick Sort
Tree Traversal	Preorder, Inorder, Postorder
Graph Search	DFS
Backtracking	N-Queens, Sudoku, Word Search
Combinatorics	Permutations, Combinations
Dynamic Programming	Fibonacci, Knapsack, LCS

🧐 MAANG-style Recursive Interview Questions

Generate Parentheses: Given n, generate all combinations of well-formed parentheses.
N-Queens Problem: Place N queens on an N×N board so no two queens attack each other.
Word Break: Given a string and a dictionary, determine if the string can be segmented.
Subset Sum: Given a list and target, check if subset sums to target.
Letter Combinations of Phone Number: Map digits to letters, return all letter combinations.
Expression Add Operators: Add +, -, or * between digits to reach target.
Decode Ways: Given digit string, return number of ways to decode.

⚖️ Recursion vs Iteration

Feature	Recursion	Iteration
Stack Usage	Uses call stack	Uses loop construct
Elegance	Shorter, more elegant	Often more efficient
Risk	Stack overflow	Safer with large input
Performance	May be slower unless memoized	Usually faster
Use Case	Tree, graphs, backtracking	Simple loops, accumulations

🌊 Design Principles for Recursion

Think in Terms of Subproblems
Ensure Smaller Input Each Call
Always Define the Exit (Base Case)
Trace on Paper for Clarity
Use Memoization if Needed

🧳 Bonus: Memoization Example

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

print(fib(50))  # Output: 12586269025 (Instant!)

🌟 Summary

Recursion is elegant but can be dangerous if misused.
Always define base and recursive cases.
Great for tree-based, backtracking, or combinatorial problems.
Master recursion with patterns, dry-runs, and practice.

# 🧠 Recursion Practice Notebook
# Covers: factorial, fibonacci, sum of list, permutations, binary search, tower of hanoi, MAANG-style questions

# ✅ 1. Factorial

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print("Factorial of 5:", factorial(5))


# ✅ 2. Fibonacci (naive)

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print("Fibonacci of 7:", fibonacci(7))


# ✅ 3. Sum of list

def sum_list(lst):
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])

print("Sum of [1,2,3,4]:", sum_list([1, 2, 3, 4]))


# ✅ 4. Permutations of string

def permutations(s):
    if len(s) == 1:
        return [s]
    perms = []
    for i in range(len(s)):
        for p in permutations(s[:i] + s[i+1:]):
            perms.append(s[i] + p)
    return perms

print("Permutations of 'abc':", permutations("abc"))


# ✅ 5. Binary Search

def binary_search(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    return binary_search(arr, target, low, mid - 1)

arr = [1, 2, 3, 4, 5, 6, 7]
print("Index of 5:", binary_search(arr, 5, 0, len(arr) - 1))


# ✅ 6. Tower of Hanoi

def tower_of_hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    tower_of_hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    tower_of_hanoi(n - 1, auxiliary, target, source)

print("\nTower of Hanoi for 3 disks:")
tower_of_hanoi(3, 'A', 'C', 'B')


# ✅ 7. Generate Parentheses (MAANG-style)

def generate_parentheses(n):
    def backtrack(s, open_count, close_count):
        if len(s) == 2 * n:
            result.append(s)
            return
        if open_count < n:
            backtrack(s + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(s + ')', open_count, close_count + 1)

    result = []
    backtrack('', 0, 0)
    return result

print("\nGenerate Parentheses for n=3:", generate_parentheses(3))


# ✅ 8. Subset Sum (returns True if sum exists)

def subset_sum(nums, target):
    if target == 0:
        return True
    if not nums:
        return False
    return subset_sum(nums[1:], target) or subset_sum(nums[1:], target - nums[0])

print("\nSubset sum 9 in [3, 34, 4, 12, 5, 2]:", subset_sum([3, 34, 4, 12, 5, 2], 9))


# ✅ 9. Visual Call Stack: Factorial (inline print)

def factorial_trace(n):
    print(f"factorial({n}) called")
    if n == 0:
        print(f"factorial({n}) = 1")
        return 1
    result = n * factorial_trace(n - 1)
    print(f"factorial({n}) = {n} * factorial({n - 1}) = {result}")
    return result

print("\nTrace of factorial(4):")
factorial_trace(4)


# ✅ 10. Visual Tree: Permutation Tree for "abc"

def print_permutation_tree(s, depth=0):
    indent = "  " * depth
    print(f"{indent}permute('{s}')")
    if len(s) == 1:
        print(f"{indent}=> return ['{s}']")
        return [s]
    result = []
    for i in range(len(s)):
        char = s[i]
        rest = s[:i] + s[i+1:]
        for sub in print_permutation_tree(rest, depth + 1):
            combined = char + sub
            result.append(combined)
            print(f"{indent}Adding: {combined}")
    return result

print("\nVisual permutation tree for 'abc':")
print_permutation_tree("abc")

# 🚀 Simulated MAANG Coding Round: Recursive Problems
# Includes test cases and edge case hints

### ✅ Problem 1: Generate All Valid Parentheses ###
# Given n pairs of parentheses, generate all valid combinations.
def generate_parentheses(n):
    def backtrack(s, open_count, close_count):
        if len(s) == 2 * n:
            result.append(s)
            return
        if open_count < n:
            backtrack(s + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(s + ')', open_count, close_count + 1)

    result = []
    backtrack('', 0, 0)
    return result

print("\nProblem 1:")
print("n = 3 =>", generate_parentheses(3))


### ✅ Problem 2: Letter Combinations of Phone Number ###
# Return all possible letter combinations that the number could represent.

phone_map = {
    "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
    "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
}

def letter_combinations(digits):
    if not digits:
        return []

    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return
        for char in phone_map[digits[index]]:
            backtrack(index + 1, path + char)

    result = []
    backtrack(0, '')
    return result

print("\nProblem 2:")
print("Digits = '23' =>", letter_combinations("23"))


### ✅ Problem 3: Subsets (Power Set) ###
# Return all possible subsets of the given list.
def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

print("\nProblem 3:")
print("Subsets of [1,2,3] =>", subsets([1, 2, 3]))


### ✅ Problem 4: Decode Ways ###
# Given a digit string, return the number of ways to decode it (A=1, ..., Z=26)
def num_decodings(s):
    memo = {}

    def dfs(i):
        if i in memo:
            return memo[i]
        if i == len(s):
            return 1
        if s[i] == '0':
            return 0
        res = dfs(i + 1)
        if i + 1 < len(s) and int(s[i:i+2]) <= 26:
            res += dfs(i + 2)
        memo[i] = res
        return res

    return dfs(0)

print("\nProblem 4:")
print("Ways to decode '226' =>", num_decodings("226"))


### ✅ Problem 5: Expression Add Operators ###
# Given a string num and an integer target, return all expressions that evaluate to target.
def add_operators(num, target):
    result = []

    def backtrack(index, prev_operand, current_total, expression):
        if index == len(num):
            if current_total == target:
                result.append(expression)
            return
        for i in range(index, len(num)):
            temp_str = num[index:i + 1]
            if len(temp_str) > 1 and temp_str[0] == "0":
                break
            current = int(temp_str)
            if index == 0:
                backtrack(i + 1, current, current, temp_str)
            else:
                backtrack(i + 1, current, current_total + current, expression + '+' + temp_str)
                backtrack(i + 1, -current, current_total - current, expression + '-' + temp_str)
                backtrack(i + 1, prev_operand * current,
                          current_total - prev_operand + (prev_operand * current),
                          expression + '*' + temp_str)

    backtrack(0, 0, 0, '')
    return result

print("\nProblem 5:")
print("Expressions for '123' to get 6 =>", add_operators("123", 6))

HintsToday

recent posts

about