🧩 Python DSA Patterns — Recursion Basics 🔁🐍

Recursion is when a function calls itself to solve a smaller instance of the same problem.

It’s one of the most important programming patterns, forming the foundation for divide & conquer and backtracking algorithms.

📝 Factorial of a Number

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

print("Factorial of 5:", factorial(5))  # Output: 120

📝 Fibonacci Sequence

def fibonacci(n: int) -> int:
    if n == 0:  # base case
        return 0
    if n == 1:  # base case
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

print("Fibonacci(6):", fibonacci(6))  # Output: 8

✅ Takeaway

• Always define a base case to stop recursion.
• Each step should move towards the base case.
• Recursion = elegant for problems that can be broken into smaller subproblems.

🏋️ Practice Problems

1. Factorial of n
2. Fibonacci series
3. Sum of digits of a number
4. Reverse a string

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns