Recursion: Functions Calling Themselves

Recursion: Functions Calling Themselves

Recursion is when a function calls itself to solve a problem by breaking it into smaller, similar subproblems. This technique is fundamental to tree structures, search algorithms, and many AI applications including decision trees and graph traversal.

Understanding Recursion Basics

Every recursive function needs a base case (stopping condition) and a recursive case (calling itself with simpler input).

# Example 1: Countdown
def countdown(n):
    # Base case: stop when n reaches 0
    if n == 0:
        print("Blastoff!")
        return
    # Recursive case: print n and call with n-1
    print(n)
    countdown(n - 1)

countdown(5)
# Output:
# 5
# 4
# 3
# 2
# 1
# Blastoff!

# Example 2: Calculate factorial
# 5! = 5 * 4 * 3 * 2 * 1 = 120
def factorial(n):
    # Base case
    if n <= 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

print(f"5! = {factorial(5)}")  # 120
print(f"10! = {factorial(10)}")  # 3628800

# Example 3: Sum of numbers
def sum_numbers(n):
    # Base case: sum of 1 is 1
    if n == 1:
        return 1
    # Recursive case: n + sum of (n-1)
    return n + sum_numbers(n - 1)

print(f"Sum 1 to 5: {sum_numbers(5)}")  # 1+2+3+4+5 = 15
print(f"Sum 1 to 100: {sum_numbers(100)}")  # 5050

Fibonacci Sequence with Recursion

The Fibonacci sequence appears in nature, art, and computer science. Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21...

# Simple recursive Fibonacci
def fibonacci(n):
    # Base cases
    if n <= 1:
        return n
    # Recursive case: sum previous two Fibonacci numbers
    return fibonacci(n - 1) + fibonacci(n - 2)

print("Fibonacci sequence:")
for i in range(10):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

# This is inefficient! Many calculations repeat
# Better approach: use memoization (remember previous results)
def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# Much faster!
print(f"
Fibonacci(30) = {fibonacci_memo(30)}")  # Still computes quickly

Recursion with Strings and Lists

Recursion works beautifully with text and list processing.

# Reverse a string
def reverse_string(s):
    # Base case: empty or single character
    if len(s) <= 1:
        return s
    # Recursive: return last char + reverse of rest
    return s[-1] + reverse_string(s[:-1])

print(f"Reverse of 'BHARAT': {reverse_string('BHARAT')}")  # TARAHB

# Check if string is palindrome (reads same forwards and backwards)
def is_palindrome(s):
    # Remove spaces and convert to lowercase
    s = s.replace(" ", "").lower()
    # Base case: if length is 0 or 1, it's a palindrome
    if len(s) <= 1:
        return True
    # Recursive: check if first and last match, then check middle
    if s[0] == s[-1]:
        return is_palindrome(s[1:-1])
    return False

print(is_palindrome("racecar"))  # True
print(is_palindrome("A man a plan a canal Panama"))  # True
print(is_palindrome("hello"))  # False

# Sum all numbers in nested list
def sum_nested_list(lst):
    total = 0
    for item in lst:
        if isinstance(item, list):
            # Recursive call for nested lists
            total += sum_nested_list(item)
        else:
            total += item
    return total

nested = [1, [2, 3], [4, [5, 6]], 7]
print(f"
Sum of {nested} = {sum_nested_list(nested)}")  # 1+2+3+4+5+6+7 = 28

Binary Search with Recursion

Binary search efficiently finds values in sorted lists—crucial for AI applications.

# Binary search: divide and conquer
def binary_search(arr, target, low, high):
    # Base case: target not found
    if low > high:
        return -1

    mid = (low + high) // 2

    # Base case: found the target
    if arr[mid] == target:
        return mid

    # Recursive cases
    if arr[mid] > target:
        # Search left half
        return binary_search(arr, target, low, mid - 1)
    else:
        # Search right half
        return binary_search(arr, target, mid + 1, high)

# Sorted list of student IDs
student_ids = [1005, 1012, 1023, 1034, 1045, 1056, 1067, 1078]
target_id = 1045

result = binary_search(student_ids, target_id, 0, len(student_ids) - 1)
print(f"
Searching for ID {target_id}:")
if result != -1:
    print(f"Found at index {result}")
else:
    print("Not found")

# Binary search is O(log n) - much faster than linear search O(n)
print("
Binary search efficiency: O(log n) vs Linear search O(n)")
print("For 1 million items:")
print(f"  Linear search: up to 1,000,000 checks")
print(f"  Binary search: up to {len(bin(1000000)) - 2} checks")

Tree Traversal with Recursion

Trees are hierarchical data structures. Recursion naturally traverses them.

# Simple tree structure
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Create a simple tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# In-order traversal (left, root, right)
def inorder_traversal(node):
    if node is None:
        return
    inorder_traversal(node.left)       # Left
    print(node.value, end=" ")          # Root
    inorder_traversal(node.right)       # Right

print("
In-order traversal: ", end="")
inorder_traversal(root)  # Output: 4 2 5 1 3

# Calculate tree height
def tree_height(node):
    if node is None:
        return 0
    left_height = tree_height(node.left)
    right_height = tree_height(node.right)
    return 1 + max(left_height, right_height)

print(f"
Tree height: {tree_height(root)}")  # 3

Key Takeaways

• Recursion requires a base case (stop condition) and recursive case (calling itself)
• Each recursive call uses a new stack frame, storing local variables
• Use recursion for problems naturally expressed as smaller subproblems
• Memoization caches results to avoid redundant recursive calls
• Binary search using recursion is O(log n)—very efficient for large datasets
• Recursion naturally handles tree structures and hierarchical data
• Be careful of infinite recursion—always ensure the base case is reachable

Under the Hood: Recursion: Functions Calling Themselves

Here is what separates someone who merely USES technology from someone who UNDERSTANDS it: knowing what happens behind the screen. When you tap "Send" on a WhatsApp message, do you know what journey that message takes? When you search something on Google, do you know how it finds the answer among billions of web pages in less than a second? When UPI processes a payment, what makes sure the money goes to the right person?

Understanding Recursion: Functions Calling Themselves gives you the ability to answer these questions. More importantly, it gives you the foundation to BUILD things, not just use things other people built. India's tech industry employs over 5 million people, and companies like Infosys, TCS, Wipro, and thousands of startups are all built on the concepts we are about to explore.

This is not just theory for exams. This is how the real world works. Let us get into it.

Object-Oriented Programming: Modelling the Real World

OOP lets you model real-world entities as code "objects." Each object has properties (data) and methods (behaviour). Here is a practical example:

class BankAccount:
    """A simple bank account — like what SBI or HDFC uses internally"""

    def __init__(self, holder_name, initial_balance=0):
        self.holder = holder_name
        self.balance = initial_balance    # Private in practice
        self.transactions = []            # History log

    def deposit(self, amount):
        if amount <= 0:
            raise ValueError("Deposit must be positive")
        self.balance += amount
        self.transactions.append(f"+₹{amount}")
        return self.balance

    def withdraw(self, amount):
        if amount > self.balance:
            raise ValueError("Insufficient funds!")
        self.balance -= amount
        self.transactions.append(f"-₹{amount}")
        return self.balance

    def statement(self):
        print(f"
--- Account Statement: {self.holder} ---")
        for t in self.transactions:
            print(f"  {t}")
        print(f"  Balance: ₹{self.balance}")

# Usage
acc = BankAccount("Rahul Sharma", 5000)
acc.deposit(15000)      # Salary credited
acc.withdraw(2000)      # UPI payment to Swiggy
acc.withdraw(500)       # Metro card recharge
acc.statement()

This is encapsulation — bundling data and behaviour together. The user of BankAccount does not need to know HOW deposit works internally; they just call it. Inheritance lets you extend this: a SavingsAccount could inherit from BankAccount and add interest calculation. Polymorphism means different account types can respond to the same .withdraw() method differently (savings accounts might check minimum balance, current accounts might allow overdraft).

Real-World System Design: Swiggy's Architecture

When you order food on Swiggy, here is what happens behind the scenes in about 2 seconds: your location is geocoded (algorithms), nearby restaurants are queried from a spatial index (data structures), menu prices are pulled from a database (SQL), delivery time is estimated using ML models trained on historical data (AI), the order is placed in a distributed message queue (Kafka), a delivery partner is assigned using a matching algorithm (optimization), and real-time tracking begins using WebSocket connections (networking). EVERY concept in your CS curriculum is being used simultaneously to deliver your biryani.

How the Web Request Cycle Works

Every time you visit a website, a precise sequence of events occurs. Here is the flow:

    You (Browser)          DNS Server          Web Server
        |                      |                    |
        |---[1] bharath.ai --->|                    |
        |                      |                    |
        |<--[2] IP: 76.76.21.9|                    |
        |                      |                    |
        |---[3] GET /index.html ----------------->  |
        |                      |                    |
        |                      |    [4] Server finds file,
        |                      |        runs server code,
        |                      |        prepares response
        |                      |                    |
        |<---[5] HTTP 200 OK + HTML + CSS + JS --- |
        |                      |                    |
   [6] Browser parses HTML                          |
       Loads CSS (styling)                          |
       Executes JS (interactivity)                  |
       Renders final page                           |

Step 1-2 is DNS resolution — converting a human-readable domain name to a machine-readable IP address. Step 3 is the HTTP request. Step 4 is server-side processing (this is where frameworks like Node.js, Django, or Flask operate). Step 5 is the HTTP response. Step 6 is client-side rendering (this is where React, Angular, or Vue operate).

In a real-world scenario, this cycle also involves CDNs (Content Delivery Networks), load balancers, caching layers, and potentially microservices. Indian companies like Jio use this exact architecture to serve 400+ million subscribers.

Production Engineering: Recursion: Functions Calling Themselves at Scale

Understanding recursion: functions calling themselves at an academic level is necessary but not sufficient. Let us examine how these concepts manifest in production environments where failure has real consequences.

Consider India's UPI system processing 10+ billion transactions monthly. The architecture must guarantee: atomicity (a transfer either completes fully or not at all — no half-transfers), consistency (balances always add up correctly across all banks), isolation (concurrent transactions on the same account do not interfere), and durability (once confirmed, a transaction survives any failure). These are the ACID properties, and violating any one of them in a payment system would cause financial chaos for millions of people.

At scale, you also face the thundering herd problem: what happens when a million users check their exam results at the same time? (CBSE result day, anyone?) Without rate limiting, connection pooling, caching, and graceful degradation, the system crashes. Good engineering means designing for the worst case while optimising for the common case. Companies like NPCI (the organisation behind UPI) invest heavily in load testing — simulating peak traffic to identify bottlenecks before they affect real users.

Monitoring and observability become critical at scale. You need metrics (how many requests per second? what is the 99th percentile latency?), logs (what happened when something went wrong?), and traces (how did a single request flow through 15 different microservices?). Tools like Prometheus, Grafana, ELK Stack, and Jaeger are standard in Indian tech companies. When Hotstar streams IPL to 50 million concurrent users, their engineering team watches these dashboards in real-time, ready to intervene if any metric goes anomalous.

The career implications are clear: engineers who understand both the theory (from chapters like this one) AND the practice (from building real systems) command the highest salaries and most interesting roles. India's top engineering talent earns ₹50-100+ LPA at companies like Google, Microsoft, and Goldman Sachs, or builds their own startups. The foundation starts here.

Key Vocabulary

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

💡 Interview-Style Problem

Here is a problem that frequently appears in technical interviews at companies like Google, Amazon, and Flipkart: "Design a URL shortener like bit.ly. How would you generate unique short codes? How would you handle millions of redirects per second? What database would you use and why? How would you track click analytics?"

Think about: hash functions for generating short codes, read-heavy workload (99% redirects, 1% creates) suggesting caching, database choice (Redis for cache, PostgreSQL for persistence), and horizontal scaling with consistent hashing. Try sketching the system architecture on paper before looking up solutions. The ability to think through system design problems is the single most valuable skill for senior engineering roles.

Where This Takes You

The knowledge you have gained about recursion: functions calling themselves is directly applicable to: competitive programming (Codeforces, CodeChef — India has the 2nd largest competitive programming community globally), open-source contribution (India is the 2nd largest contributor on GitHub), placement preparation (these concepts form 60% of technical interview questions), and building real products (every startup needs engineers who understand these fundamentals).

India's tech ecosystem offers incredible opportunities. Freshers at top companies earn ₹15-50 LPA; experienced engineers at FAANG companies in India earn ₹50-1 Cr+. But more importantly, the problems being solved in India — digital payments for 1.4 billion people, healthcare AI for rural areas, agricultural tech for 150 million farmers — are some of the most impactful engineering challenges in the world. The fundamentals you are building will be the tools you use to tackle them.

Crafted for Class 7–9 • Programming & Coding • Aligned with NEP 2020 & CBSE Curriculum