Recursion & Backtracking – Deep Dive | Learn Python+

Recursion – A Function Calling Itself

Every recursive function needs two parts:

Base case – the simplest version of the problem (stops recursion).
Recursive case – reduces the problem and calls itself again.

The call stack remembers each call until the base case returns.

recursive_countdown.py

def countdown(n):
    if n == 0:           # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)     # recursive case

countdown(3)

3 2 1 Go!

Factorial – A Classic First Step

Factorial of n = n × (n‑1) × … × 1. Base case: 0! = 1.

factorial.py

def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case

print(factorial(5))     # 120

120

📌 Note: factorial(1000) will exceed the default recursion depth. We'll later use iteration or lru_cache for deep recursion.

Fibonacci Sequence

Fibonacci series: 0, 1, 1, 2, 3, 5, 8, … where F(n) = F(n‑1) + F(n‑2). Naive recursion is extremely inefficient, but we can fix it with memoisation.

fibonacci_naive.py

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

print(fib(10))   # 55

Backtracking – Explore & Undo

Backtracking builds candidates step by step and abandons (“backtracks”) any candidate as soon as it determines the candidate cannot lead to a valid solution. It follows the pattern choose → explore → unchoose (recursive). Ideal for generating all subsets, permutations, or valid parentheses combinations.

Generate Parentheses (LeetCode 22)

Given n pairs of parentheses, write a function to generate all combinations of well‑formed parentheses.

generate_parentheses.py

def generateParenthesis(n):
    result = []
    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:   # base: used all pairs
            result.append(current)
            return
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return result

print(generateParenthesis(3))

['((()))', '(()())', '(())()', '()(())', '()()()']

Subsets (Power Set – LeetCode 78)

Given an array of unique elements, return all possible subsets (the power set). Backtracking builds subsets by deciding for each element whether to include it or not.

subsets_backtracking.py

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])         # snapshot current subset
        for i in range(start, len(nums)):
            path.append(nums[i])       # choose
            backtrack(i + 1, path)     # explore
            path.pop()                 # unchoose (backtrack)

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Recursion Depth & `lru_cache`

Recursion depth limit prevents stack overflow (default ~1000). You can view/set it with sys.getrecursionlimit() and sys.setrecursionlimit().

@functools.lru_cache memoises results so repeated recursive calls return instantly. It turns the slow fib(n) into a lightning‑fast version.

fib_cached.py

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(100))           # 354224848179261915075 (instant)
print(fib.cache_info())   # hits, misses, etc.

354224848179261915075 CacheInfo(hits=98, misses=101, maxsize=None, currsize=101)

Recursive Generators with `yield`

You can write recursive functions that yield values lazily, avoiding storing the entire result in memory. Use yield from to delegate to a sub‑generator.

recursive_generator.py

# Recursively flatten a nested list
def flatten(nested):
    for item in nested:
        if isinstance(item, list):
            yield from flatten(item)   # delegate recursion
        else:
            yield item

nested = [1, [2, [3, 4], 5], 6]
print(list(flatten(nested)))   # [1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

🎯 Mini Project: Permutations & Combinations Generator

This project uses recursion and backtracking to generate all permutations and combinations of a given set of items. It also uses variables, input validation, type casting, loops, conditionals, lists, sets, and dictionaries – everything you’ve learned so far. You’ll build an interactive tool that generates and displays all arrangements of a user‑provided list of elements.

permutation_combination_generator.py

"""
Permutation & Combination Generator – Complete Mini Project
Concepts used: recursion, backtracking, variables, type casting,
loops, conditionals, lists, sets, dictionaries.
"""

def main():
    # User input
    items_input = input("Enter items separated by commas (e.g., a,b,c): ").strip()
    items = [x.strip() for x in items_input.split(",") if x.strip()]
    if not items:
        print("No valid items provided. Exiting.")
        return
    
    print("\n🎲 SELECT OPTION 🎲")
    print("1. Generate all permutations")
    print("2. Generate all combinations (of all lengths)")
    choice = input("Choose (1/2): ").strip()
    
    if choice == "1":
        # Permutations (backtracking)
        result = []
        used = [False] * len(items)
        def backtrack_perm(path):
            if len(path) == len(items):
                result.append(path[:])
                return
            for i in range(len(items)):
                if not used[i]:
                    used[i] = True
                    path.append(items[i])
                    backtrack_perm(path)
                    path.pop()
                    used[i] = False
        backtrack_perm([])
        print(f"\n📌 Total permutations: {len(result)}")
        for p in result:
            print(p)
    
    elif choice == "2":
        # Combinations (backtracking, include all lengths)
        result = {}
        items_set = set(items)          # ensures uniqueness (demonstrates set)
        items = list(items_set)         # convert back to list
        for r in range(1, len(items) + 1):
            current_combs = []
            def backtrack_comb(start, path, r):
                if len(path) == r:
                    current_combs.append(path[:])
                    return
                for i in range(start, len(items)):
                    path.append(items[i])
                    backtrack_comb(i + 1, path, r)
                    path.pop()
            backtrack_comb(0, [], r)
            result[r] = current_combs
        print("\n📌 All combinations:")
        total = 0
        for r, combs in result.items():
            print(f"\nLength {r} ({len(combs)} combinations):")
            for c in combs:
                print(c)
            total += len(combs)
        print(f"\n📊 Total combinations: {total}")
    else:
        print("Invalid choice.")

if __name__ == "__main__":
    main()

💡 Project Highlights:
– Recursion & Backtracking generate permutations and combinations.
– Lists store the user‑provided items and intermediate results.
– Sets ensure unique elements before generating combinations.
– Dictionaries (optional) group combinations by length.
– Input validation and type casting handle user input.
– Loops and conditionals drive the menu and generation process.
– f‑strings format the output.
– Extend the project by adding a feature to count only unique permutations or by handling larger inputs with iterative methods.

Solved Practice Problems

🔰 Beginner Level

1. Sum of digits using recursion

def digit_sum(n):
    if n == 0: return 0
    return n % 10 + digit_sum(n // 10)

print(digit_sum(123))   # 6

2. Recursive power function (a^b)

def power(a, b):
    if b == 0: return 1
    return a * power(a, b - 1)

print(power(2, 5))   # 32

3. Print numbers from 1 to N using recursion

def print_numbers(n):
    if n == 0: return
    print_numbers(n - 1)
    print(n, end=' ')

print_numbers(5)   # 1 2 3 4 5

⚡ Intermediate Level

4. Generate all binary strings of length n (backtracking)

def binary_strings(n):
    result = []
    def backtrack(current):
        if len(current) == n:
            result.append(current)
            return
        backtrack(current + '0')
        backtrack(current + '1')
    backtrack('')
    return result

print(binary_strings(2))   # ['00', '01', '10', '11']

5. Palindrome check using recursion

def is_palindrome(s):
    s = ''.join(filter(str.isalnum, s)).lower()
    def recurse(left, right):
        if left >= right: return True
        if s[left] != s[right]: return False
        return recurse(left + 1, right - 1)
    return recurse(0, len(s)-1)

print(is_palindrome("A man, a plan, a canal: Panama"))  # True

Unsolved Exercises

Challenge yourself – no solutions provided, but you can use the solved examples and the mini project as a guide.