Recursion and Dynamic Programming

Recursion and Dynamic Programming

Imagine explaining a joke to someone, and they ask "but what does X mean?" and you explain that, and they ask again... Eventually, you reach something so simple that no more explanation is needed. That's recursion: a function explaining itself until the problem becomes trivial.

Part 1: Recursion Basics

A recursive function calls itself with a simpler version of the problem. Every recursion needs:

1. Base case: When to stop (without this, infinite loop)
2. Recursive case: How to break the problem into smaller pieces

# Example 1: Factorial
# 5! = 5 × 4 × 3 × 2 × 1 = 120

def factorial(n):
    # Base case: 0! = 1
    if n == 0:
        return 1
    # Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1)

print(factorial(5))  # 120
# Trace:
# factorial(5) = 5 * factorial(4)
# factorial(4) = 4 * factorial(3)
# factorial(3) = 3 * factorial(2)
# factorial(2) = 2 * factorial(1)
# factorial(1) = 1 * factorial(0)
# factorial(0) = 1  [BASE CASE]

Example 2: Sum of Array

def sum_array(arr, index=0):
    # Base case: reached end
    if index == len(arr):
        return 0
    # Recursive case: current element + sum of rest
    return arr[index] + sum_array(arr, index + 1)

print(sum_array([1, 2, 3, 4, 5]))  # 15

Example 3: Binary Search (Efficient!)

def binary_search(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    # Base case: element not found
    if left > right:
        return -1

    mid = (left + right) // 2

    # Found it!
    if arr[mid] == target:
        return mid
    # Search left half
    elif arr[mid] > target:
        return binary_search(arr, target, left, mid - 1)
    # Search right half
    else:
        return binary_search(arr, target, mid + 1, right)

arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))   # 3 (index of 7)
print(binary_search(arr, 10))  # -1 (not found)

Part 2: When Recursion Gets Slow—The Fibonacci Problem

# Naive recursion: VERY SLOW
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

print(fib_slow(10))  # 55 — works
print(fib_slow(40))  # Takes SECONDS (billions of function calls)

# Why is it slow? Let's count function calls
# fib(5) calls fib(4) and fib(3)
# fib(4) calls fib(3) and fib(2)
# fib(3) is computed TWICE!
# fib(2) is computed multiple times!
# This is exponential time complexity: O(2ⁿ) — terrible!

Part 3: Memoization—Remember Previous Answers

Cache previously computed results. When asked for fib(3) again, look it up instead of recomputing.

# Memoization with Python decorator
def memoize(func):
    cache = {}
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]
    return wrapper

@memoize
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(40))  # Instant! (linear time O(n))

# Manual memoization for clarity
def fib_memo_manual(n, memo={}):
    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    memo[n] = fib_memo_manual(n - 1, memo) + fib_memo_manual(n - 2, memo)
    return memo[n]

print(fib_memo_manual(40))  # 102334155

Part 4: Dynamic Programming—Building Solutions Bottom-Up

Instead of recursion (top-down), we build solutions from smallest subproblems upward (bottom-up).

# Dynamic Programming: Fibonacci iteratively
def fib_dp(n):
    if n <= 1:
        return n

    # dp[i] = fibonacci number for i
    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

print(fib_dp(40))  # 102334155 (fast and clean)

# Space-optimized DP (we only need last 2 values)
def fib_dp_optimized(n):
    if n <= 1:
        return n

    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

print(fib_dp_optimized(40))  # 102334155 (O(n) time, O(1) space)

Part 5: Coin Change Problem (Classic DP)

Problem: You have coins of denominations [1, 2, 5]. What's the minimum number of coins needed to make ₹11?

def min_coins(amount, coins):
    # dp[i] = minimum coins needed to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 coins needed for amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                # Use this coin and check if better
                dp[i] = min(dp[i], 1 + dp[i - coin])

    return dp[amount]

coins = [1, 2, 5]
print(min_coins(11, coins))  # 3 (5 + 5 + 1)
print(min_coins(13, coins))  # 3 (5 + 5 + 2 + 1 won't work, it's 5+5+2+1=4, actually 5+5+3 but 3 isn't a coin... answer is 4 with coins 5,5,2,1 OR 5+2+2+2+2=5... Actually: 11 = 5+5+1 = 3 coins)

# Let's trace for amount = 11:
# dp[0] = 0
# dp[1] = 1 (one 1-coin)
# dp[2] = 1 (one 2-coin)
# dp[3] = 2 (2+1)
# dp[4] = 2 (2+2)
# dp[5] = 1 (one 5-coin)
# dp[6] = 2 (5+1)
# dp[7] = 2 (5+2)
# dp[8] = 3 (5+2+1)
# dp[9] = 3 (5+2+2)
# dp[10] = 2 (5+5)
# dp[11] = 3 (5+5+1)

Part 6: Tower of Hanoi (Classic Recursion Problem)

Problem: Move N disks from rod A to rod C, using rod B as auxiliary. Rules:

• Move one disk at a time
• Never place larger disk on smaller disk

def hanoi(n, source, destination, auxiliary):
    # Base case: only one disk
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return

    # Move n-1 disks from source to auxiliary (using destination)
    hanoi(n - 1, source, auxiliary, destination)

    # Move largest disk from source to destination
    print(f"Move disk {n} from {source} to {destination}")

    # Move n-1 disks from auxiliary to destination (using source)
    hanoi(n - 1, auxiliary, destination, source)

print("Tower of Hanoi with 3 disks:")
hanoi(3, 'A', 'C', 'B')
# Output:
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C
# (7 moves = 2³-1 = 7)

The minimum moves for n disks is 2ⁿ - 1. For n=64 disks (the legend of the tower), it's 2⁶⁴ - 1 = 18,446,744,073,709,551,615 moves!

Part 7: Longest Common Subsequence (LCS)—DP Problem

Problem: Given two strings, find the longest subsequence common to both.

def lcs(text1, text2):
    m, n = len(text1), len(text2)

    # dp[i][j] = LCS length of text1[0:i] and text2[0:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                # Characters match
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                # Characters don't match, take best of two options
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

print(lcs("abcde", "ace"))      # 3 (ace)
print(lcs("abc", "abc"))         # 3
print(lcs("xyz", "abc"))         # 0
print(lcs("AGGTAB", "GXTXAYB"))  # 5 (GTAB)

# Trace for lcs("ab", "ac"):
#     ""  a  c
# ""   0  0  0
# a    0  1  1
# b    0  1  1
# Result: 1 (the 'a')

Part 8: Complexity Analysis

Part 9: When to Use What

Use Recursion when:

• The problem has a natural recursive structure (trees, divide-and-conquer)
• Code clarity is more important than performance
• Problem size is small

Use DP when:

• Subproblems overlap (can reuse solutions)
• Need optimal solutions
• Performance matters

Your goal: Solve 20 recursion/DP problems on an online judge (LeetCode, CodeChef, Codeforces). Master these, and interviews become much easier!

Deep Dive: Recursion and Dynamic Programming

At this level, we stop simplifying and start engaging with the real complexity of Recursion and Dynamic Programming. In production systems at companies like Flipkart, Razorpay, or Swiggy — all Indian companies processing millions of transactions daily — the concepts in this chapter are not academic exercises. They are engineering decisions that affect system reliability, user experience, and ultimately, business success.

The Indian tech ecosystem is at an inflection point. With initiatives like Digital India and India Stack (Aadhaar, UPI, DigiLocker), the country has built technology infrastructure that is genuinely world-leading. Understanding the technical foundations behind these systems — which is what this chapter covers — positions you to contribute to the next generation of Indian technology innovation.

Whether you are preparing for JEE, GATE, campus placements, or building your own products, the depth of understanding we develop here will serve you well. Let us go beyond surface-level knowledge.

Design Patterns and Production-Grade Code

Writing code that works is step one. Writing code that is maintainable, testable, and scalable is software engineering. Here is an example using the Strategy pattern — commonly asked in interviews:

from abc import ABC, abstractmethod

# Strategy Pattern — different payment methods
class PaymentStrategy(ABC):
    @abstractmethod
    def pay(self, amount: float) -> bool:
        pass

class UPIPayment(PaymentStrategy):
    def __init__(self, upi_id: str):
        self.upi_id = upi_id

    def pay(self, amount: float) -> bool:
        # In reality: call NPCI API, verify, debit
        print(f"Paid ₹{amount} via UPI ({self.upi_id})")
        return True

class CardPayment(PaymentStrategy):
    def __init__(self, card_number: str):
        self.card = card_number[-4:]  # Store only last 4

    def pay(self, amount: float) -> bool:
        print(f"Paid ₹{amount} via Card (****{self.card})")
        return True

class ShoppingCart:
    def __init__(self):
        self.items = []

    def add(self, item: str, price: float):
        self.items.append((item, price))

    def checkout(self, payment: PaymentStrategy):
        total = sum(p for _, p in self.items)
        return payment.pay(total)

# Usage — payment method is injected, not hardcoded
cart = ShoppingCart()
cart.add("Python Book", 599)
cart.add("USB Cable", 199)
cart.checkout(UPIPayment("rahul@okicici"))  # Easy to swap!

The Strategy pattern decouples the payment mechanism from the cart logic. Adding a new payment method (Wallet, Net Banking, EMI) requires ZERO changes to ShoppingCart — you just create a new strategy class. This is the Open/Closed Principle: open for extension, closed for modification. This exact pattern is how Razorpay, Paytm, and PhonePe handle their multiple payment gateways internally.

India's Scale Challenges: Engineering for 1.4 Billion

Building technology for India presents unique engineering challenges that make it one of the most interesting markets in the world. UPI handles 10 billion transactions per month — more than all credit card transactions in the US combined. Aadhaar authenticates 100 million identities daily. Jio's network serves 400 million subscribers across 22 telecom circles. Hotstar streamed IPL to 50 million concurrent viewers — a world record. Each of these systems must handle India's diversity: 22 official languages, 28 states with different regulations, massive urban-rural connectivity gaps, and price-sensitive users expecting everything to work on ₹7,000 smartphones over patchy 4G connections. This is why Indian engineers are globally respected — if you can build systems that work in India, they will work anywhere.

Modern Web Architecture: Client-Server to Microservices

Production web systems have evolved far beyond simple client-server. Here is how a modern web application like Flipkart or Swiggy is architected:

┌──────────────┐     ┌──────────────┐     ┌──────────────────────────────┐
│   Browser    │────▶│  CDN / Edge  │────▶│        Load Balancer          │
│  (React SPA) │     │  (Cloudflare)│     │    (NGINX / AWS ALB)          │
└──────────────┘     └──────────────┘     └──────────┬───────────────────┘
                                                      │
                          ┌───────────────────────────┼────────────────────┐
                          │                           │                    │
                   ┌──────▼──────┐  ┌────────────────▼──┐  ┌─────────────▼─────┐
                   │ Auth Service│  │  Product Service   │  │  Order Service     │
                   │  (Node.js)  │  │  (Java/Spring)     │  │  (Go)              │
                   └──────┬──────┘  └────────┬───────────┘  └──────────┬────────┘
                          │                  │                         │
                   ┌──────▼──────┐  ┌────────▼──────┐  ┌──────────────▼────────┐
                   │  Redis      │  │  PostgreSQL    │  │  MongoDB + Kafka      │
                   │  (Sessions) │  │  (Catalog)     │  │  (Orders + Events)    │
                   └─────────────┘  └───────────────┘  └───────────────────────┘

Each microservice owns its data, communicates via REST APIs or message queues (Kafka), and can be scaled independently. When Flipkart runs a Big Billion Days sale, they scale the Order Service to handle 100x normal load without touching the Auth Service. This is the microservices pattern, and understanding it is essential for system design interviews at any top company.

Key concepts: API Gateway pattern, service discovery (Consul/Eureka), circuit breakers (Hystrix), event-driven architecture (Kafka/RabbitMQ), containerisation (Docker/Kubernetes), and observability (distributed tracing with Jaeger, metrics with Prometheus/Grafana).

Research Frontiers and Open Problems in Recursion and Dynamic Programming

Beyond production engineering, recursion and dynamic programming connects to active research frontiers where fundamental questions remain open. These are problems where your generation of computer scientists will make breakthroughs.

Quantum computing threatens to upend many of our assumptions. Shor's algorithm can factor large numbers efficiently on a quantum computer, which would break RSA encryption — the foundation of internet security. Post-quantum cryptography is an active research area, with NIST standardising new algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium) that resist quantum attacks. Indian researchers at IISER, IISc, and TIFR are contributing to both quantum computing hardware and post-quantum cryptographic algorithms.

AI safety and alignment is another frontier with direct connections to recursion and dynamic programming. As AI systems become more capable, ensuring they behave as intended becomes critical. This involves formal verification (mathematically proving system properties), interpretability (understanding WHY a model makes certain decisions), and robustness (ensuring models do not fail catastrophically on edge cases). The Alignment Research Center and organisations like Anthropic are working on these problems, and Indian researchers are increasingly contributing.

Edge computing and the Internet of Things present new challenges: billions of devices with limited compute and connectivity. India's smart city initiatives and agricultural IoT deployments (soil sensors, weather stations, drone imaging) require algorithms that work with intermittent connectivity, limited battery, and constrained memory. This is fundamentally different from cloud computing and requires rethinking many assumptions.

Finally, the ethical dimensions: facial recognition in public spaces (deployed in several Indian cities), algorithmic bias in loan approvals and hiring, deepfakes in political campaigns, and data sovereignty questions about where Indian citizens' data should be stored. These are not just technical problems — they require CS expertise combined with ethics, law, and social science. The best engineers of the future will be those who understand both the technical implementation AND the societal implications. Your study of recursion and dynamic programming is one step on that path.

Key Vocabulary

Here are important terms from this chapter that you should know:

🏗️ Architecture Challenge

Design the backend for India's election results system. Requirements: 10 lakh (1 million) polling booths reporting simultaneously, results must be accurate (no double-counting), real-time aggregation at constituency and state levels, public dashboard handling 100 million concurrent users, and complete audit trail. Consider: How do you ensure exactly-once delivery of results? (idempotency keys) How do you aggregate in real-time? (stream processing with Apache Flink) How do you serve 100M users? (CDN + read replicas + edge computing) How do you prevent tampering? (digital signatures + blockchain audit log) This is the kind of system design problem that separates senior engineers from staff engineers.

The Frontier

You now have a deep understanding of recursion and dynamic programming — deep enough to apply it in production systems, discuss tradeoffs in system design interviews, and build upon it for research or entrepreneurship. But technology never stands still. The concepts in this chapter will evolve: quantum computing may change our assumptions about complexity, new architectures may replace current paradigms, and AI may automate parts of what engineers do today.

What will NOT change is the ability to think clearly about complex systems, to reason about tradeoffs, to learn quickly and adapt. These meta-skills are what truly matter. India's position in global technology is only growing stronger — from the India Stack to ISRO to the startup ecosystem to open-source contributions. You are part of this story. What you build next is up to you.

Crafted for Class 10–12 • Algorithms & Competitive Programming • Aligned with NEP 2020 & CBSE Curriculum