A comprehensive educational package demonstrating recursive programming patterns, algorithms, and techniques in Python. This package provides well-documented implementations of fundamental and advanced recursive algorithms, complete with complexity analysis and practical examples.
- 40+ Recursive Functions organized into 5 categories
- Comprehensive Documentation with time and space complexity analysis
- Type Hints for all functions using Python 3.9+ syntax
- Full Test Coverage with pytest
- Interactive CLI for exploring recursion patterns
- Educational Focus with detailed explanations and examples
pip install -e .For development with testing:
pip install -e ".[dev]"from recursion_examples import factorial, fibonacci, power, sum_digits
# Calculate factorial
result = factorial(5) # 120
# Generate Fibonacci numbers (with memoization)
fib = fibonacci_memo(10) # 55
# Calculate power
value = power(2, 8) # 256
# Sum digits of a number
total = sum_digits(12345) # 15from recursion_examples import reverse_string, is_palindrome, count_chars
# Reverse a string
reversed_text = reverse_string("hello") # "olleh"
# Check palindrome (case-insensitive)
is_valid = is_palindrome("RaceCar") # True
# Count character occurrences
count = count_chars("hello world", "l") # 3from recursion_examples import gcd, sum_range, product_range, exponential_growth
# Greatest common divisor (Euclidean algorithm)
result = gcd(48, 18) # 6
# Sum numbers in range
total = sum_range(1, 100) # 5050
# Product of range
product = product_range(1, 5) # 120 (5!)
# Exponential growth pattern
value = exponential_growth(5) # 62from recursion_examples import sum_list, find_max, flatten_list, reverse_list
# Sum all elements
total = sum_list([1, 2, 3, 4, 5]) # 15
# Find maximum value
maximum = find_max([3, 7, 2, 9, 1]) # 9
# Flatten nested lists
flat = flatten_list([[1, 2], [3, [4, 5]], 6]) # [1, 2, 3, 4, 5, 6]
# Reverse a list
reversed_list = reverse_list([1, 2, 3, 4, 5]) # [5, 4, 3, 2, 1]from recursion_examples import (
tower_of_hanoi,
generate_subsets,
permutations,
binary_search_recursive,
merge_sort,
combinations
)
# Tower of Hanoi puzzle
moves = tower_of_hanoi(3, 'A', 'C', 'B')
# Returns list of moves to solve puzzle
# Generate all subsets (power set)
subsets = generate_subsets([1, 2, 3])
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
# Generate all permutations
perms = permutations([1, 2, 3])
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
# Binary search
index = binary_search_recursive([1, 3, 5, 7, 9], 5) # 2
# Merge sort
sorted_list = merge_sort([5, 2, 8, 1, 9]) # [1, 2, 5, 8, 9]
# Generate combinations
combs = combinations([1, 2, 3, 4], 2)
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]Run the interactive CLI to explore recursion patterns:
recursion-demoOr with Python:
python -m recursion_examples.cliThe CLI includes:
- Basic recursion patterns (factorial, fibonacci, power)
- String manipulation (reverse, palindrome, character counting)
- Mathematical operations (GCD, ranges, exponential growth)
- List operations (sum, max, flatten, reverse)
- Tower of Hanoi visualization
- Combinatorics (subsets, permutations, binary search)
- Practical applications (file trees, memoization, sorting)
- Common recursion patterns explained
- Complexity analysis tables
| Function | Description | Time Complexity | Space Complexity |
|---|---|---|---|
factorial(n) |
Calculate n! | O(n) | O(n) |
fibonacci(n) |
Nth Fibonacci number (naive) | O(2^n) | O(n) |
fibonacci_memo(n) |
Nth Fibonacci with memoization | O(n) | O(n) |
power(base, exp) |
Calculate base^exp | O(exp) | O(exp) |
sum_digits(n) |
Sum digits of number | O(log n) | O(log n) |
count_down(n) |
Count down from n | O(n) | O(n) |
count_up(n) |
Count up to n | O(n) | O(n) |
| Function | Description | Time Complexity | Space Complexity |
|---|---|---|---|
reverse_string(s) |
Reverse a string | O(n) | O(n) |
is_palindrome(s) |
Check if palindrome | O(n) | O(n) |
print_suffixes(s) |
Print all suffixes | O(n^2) | O(n) |
count_chars(s, char) |
Count character occurrences | O(n) | O(n) |
string_length(s) |
Calculate string length | O(n) | O(n) |
remove_char(s, char) |
Remove all occurrences | O(n) | O(n) |
| Function | Description | Time Complexity | Space Complexity |
|---|---|---|---|
gcd(a, b) |
Greatest common divisor | O(log min(a,b)) | O(log min(a,b)) |
sum_range(start, end) |
Sum numbers in range | O(n) | O(n) |
product_range(start, end) |
Product of range | O(n) | O(n) |
exponential_growth(n) |
Pattern: 2^(k+1) | O(n) | O(n) |
sum_series(n) |
Sum 1+2+...+n | O(n) | O(n) |
multiply(a, b) |
Multiply via addition | O(b) | O(b) |
lcm(a, b) |
Least common multiple | O(log min(a,b)) | O(log min(a,b)) |
| Function | Description | Time Complexity | Space Complexity |
|---|---|---|---|
sum_list(lst) |
Sum all elements | O(n) | O(n) |
find_max(lst) |
Find maximum value | O(n) | O(n) |
find_min(lst) |
Find minimum value | O(n) | O(n) |
count_occurrences(lst, val) |
Count occurrences | O(n) | O(n) |
flatten_list(lst) |
Flatten nested lists | O(n) | O(d) where d=depth |
reverse_list(lst) |
Reverse a list | O(n) | O(n) |
is_sorted(lst) |
Check if sorted | O(n) | O(n) |
list_contains(lst, val) |
Check if contains value | O(n) | O(n) |
| Function | Description | Time Complexity | Space Complexity |
|---|---|---|---|
tower_of_hanoi(n, ...) |
Tower of Hanoi puzzle | O(2^n) | O(n) |
generate_subsets(lst) |
Generate power set | O(2^n) | O(2^n) |
permutations(lst) |
All permutations | O(n!) | O(n!) |
binary_search_recursive(lst, target) |
Binary search | O(log n) | O(log n) |
merge_sort(lst) |
Merge sort algorithm | O(n log n) | O(n) |
quick_sort(lst) |
Quick sort algorithm | O(n log n) avg | O(log n) avg |
combinations(lst, k) |
Generate combinations | O(C(n,k)) | O(C(n,k)) |
- Factorial Calculator: Understanding base cases and recursive calls
- Fibonacci Sequence: Comparing naive vs memoized implementations
- String Reversal: Character-by-character processing patterns
- Sorting Algorithms: Merge sort and quick sort with divide-and-conquer
- Search Algorithms: Binary search for efficient searching
- GCD Calculation: Euclidean algorithm for number theory
- Tower of Hanoi: Classic puzzle demonstrating recursive problem decomposition
- Combinatorics: Generating subsets, permutations, and combinations
- List Processing: Flattening nested structures, finding extremes
- Linear Recursion: Processing one element at a time (sum, count)
- Binary Recursion: Dividing problems in half (binary search)
- Backtracking: Exploring all possibilities (subsets, permutations)
- Tail Recursion: Optimizable recursive patterns
- Divide and Conquer: Breaking problems into smaller subproblems (merge sort)
Run all tests:
pytestRun with verbose output:
pytest -vRun with coverage:
pytest --cov=recursion_examples --cov-report=htmlrecursion_examples/
├── src/
│ └── recursion_examples/
│ ├── __init__.py # Package initialization and exports
│ ├── basic.py # Fundamental recursive patterns
│ ├── string_operations.py # String manipulation functions
│ ├── mathematical.py # Mathematical algorithms
│ ├── list_operations.py # List processing functions
│ ├── advanced.py # Complex algorithms
│ └── cli.py # Interactive demonstrations
├── tests/
│ └── test_recursion_examples.py # Comprehensive test suite
├── pyproject.toml # Package configuration
├── LICENSE # MIT License
└── README.md # This file
Authored 20 November, 2025 by Maxwell Hauser
This project is licensed under the MIT License - see the LICENSE file for details.