7. Functions

💡 Why this matters for DSA Functions let you break problems into reusable pieces. Recursion is the foundation of trees, graphs, divide & conquer, and backtracking.

7.1 Defining Functions

python

def add(a, b):
    return a + b

result = add(3, 5)  # 8

python

# Type hints (optional but recommended for clarity)
def is_even(n: int) -> bool:
    return n % 2 == 0

7.2 Parameters & Return Values

Default arguments

python

def greet(name, greeting="Hello"):
    return f"{greeting}, {name}!"

greet("Manik")              # "Hello, Manik!"
greet("Manik", "Hi")        # "Hi, Manik!"

⚠️ Warning — Mutable default arguments:

python

def bad(arr=[]):     # ❌ Default list is shared across calls!
    arr.append(1)
    return arr

def good(arr=None):  # ✅ Use None, create inside
    if arr is None:
        arr = []
    arr.append(1)
    return arr

Returning multiple values

python

def min_max(arr):
    return min(arr), max(arr)  # returns a tuple

low, high = min_max([3, 1, 7, 2])  # low=1, high=7

7.3 lambda Functions

Small anonymous functions — used mainly as arguments to sorted(), map(), filter().

python

# Lambda syntax: lambda args: expression
square = lambda x: x ** 2
print(square(5))  # 25

Where lambdas shine in DSA

python

# Sorting with custom key (extremely common)
arr = [(1, "z"), (3, "a"), (2, "c")]
arr.sort(key=lambda x: x[1])        # sort by second element
arr.sort(key=lambda x: x[0])        # sort by first element
arr.sort(key=lambda x: -x[0])       # sort by first descending

# Sort strings by length
words = ["python", "go", "java", "rust"]
words.sort(key=lambda w: len(w))    # ["go", "rust", "java", "python"]

# Sort by multiple criteria
students.sort(key=lambda s: (-s.score, s.name))

# Sorting with map
indexes = sorted(range(len(arr)), key=lambda i: arr[i])

✅ Tip: sorted() returns a new list, .sort() sorts in-place
python
sorted(arr, key=...)   # returns new sorted list
arr.sort(key=...)      # sorts in-place, returns None

7.4 Recursion (Intro)

A function that calls itself.

Structure

python

def recursive_fn(n):
    # Base case — stops recursion
    if n == 0:
        return 1

    # Recursive case — calls itself
    return n * recursive_fn(n - 1)

Classic examples

python

# Factorial
def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

# Fibonacci
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Recursion visualization

python

fact(4) = 4 * fact(3)
             fact(3) = 3 * fact(2)
                          fact(2) = 2 * fact(1)
                                       fact(1) = 1  ← base case
                          fact(2) = 2 * 1 = 2
             fact(3) = 3 * 2 = 6
fact(4) = 4 * 6 = 24

⚠️ Warning — Recursion limits: Python has a recursion limit (~1000). Use iteration or increase limit for deep recursion:
python
import sys
sys.setrecursionlimit(10**6)

When to use recursion in DSA

Problem	Why recursion
Tree traversal	Natural recursive structure
Graph DFS	Simple with recursion
Divide & conquer (merge sort, quick sort)	Split → recurse → combine
Backtracking (N-Queens, permutations)	Try → recurse → undo
Fibonacci / DP	Recurrence relation

✅ Tip — Recursion vs Iteration:

Recursion: cleaner code for naturally recursive problems

Iteration: better performance, no stack overflow

Many DSA problems expect recursive solutions (trees, graphs)

Practice Drill

python

# 1. Write a function that checks if a number is prime
# 2. Sort a list of strings by their last character
# 3. Write a recursive function to compute sum of n natural numbers
# 4. Write a recursive function to reverse a string

💡 Click for Solutions

python

# 1. Prime check
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

print(is_prime(17))  # True

# 2. Sort by last character
words = ["banana", "apple", "cherry", "date"]
words.sort(key=lambda w: w[-1])
print(words)  # ['banana', 'apple', 'date', 'cherry']

# 3. Sum of n natural numbers (recursive)
def sum_n(n):
    if n == 0:
        return 0
    return n + sum_n(n - 1)

print(sum_n(5))  # 15

# 4. Reverse a string (recursive)
def reverse(s):
    if len(s) <= 1:
        return s
    return reverse(s[1:]) + s[0]

print(reverse("hello"))  # "olleh"

← Conditionals & Loops | Next → Built-in Functions & Modules