Explain the fundamental concept of recursion and its applications in programming.

What is Recursion?

Recursion is a programming technique where a function calls itself with updated arguments to solve a problem by breaking it into smaller, self-similar sub-problems.

Every recursive solution has two essential parts:

Part	Description
Base case	The condition that stops the recursion — a problem so simple it can be solved directly without further calls
Recursive case	The function calls itself with a smaller or simpler version of the original problem

---

Example: Factorial

$n! = n \times (n-1) \times (n-2) \times \dots \times 1$

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

Trace:

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

---

The Call Stack

Each recursive call pushes a new stack frame onto the call stack. When the base case is reached, frames unwind as each call returns its result to the one below it.

factorial(4)     ← returns 24
    factorial(3)  ← returns 6
        factorial(2)  ← returns 2
            factorial(1)  ← returns 1
                factorial(0)  ← returns 1 (base case)

---

Tracing Recursive Algorithms

Example: Sum of a list

def sum_list(arr):
    if len(arr) == 0:         # Base case: empty list
        return 0
    return arr[0] + sum_list(arr[1:])  # Recursive case

sum_list([1, 2, 3, 4])
= 1 + sum_list([2, 3, 4])
= 1 + (2 + sum_list([3, 4]))
= 1 + (2 + (3 + sum_list([4])))
= 1 + (2 + (3 + (4 + sum_list([]))))
= 1 + (2 + (3 + (4 + 0)))
= 1 + (2 + (3 + 4))
= 1 + (2 + 7)
= 1 + 9
= 10

---

When to Use Recursion

Use case	Why recursion fits
Tree traversal	Tree nodes have child subtrees — natural recursive structure
Graph traversal (DFS)	Explore a node, then recursively explore all neighbors
Sorting (merge sort, quicksort)	Divide the list into halves, recursively sort each half
Computing mathematical sequences	Fibonacci, factorial, power of a number
Searching (binary search)	Recursively search the appropriate half
Backtracking	Try a step, recurse, undo if it fails
Directory/file traversal	Folders contain subfolders — natural recursion

---

Recursion vs Iteration

Property	Recursion	Iteration
Memory	O(n) call stack frames	O(1) — no extra frames
Readability	Cleaner for tree/graph problems	More verbose for recursive problems
Stack overflow risk	Yes — deep recursion can overflow	No — loops don’t overflow
Speed	Slower — function call overhead	Faster — no call overhead
Termination	Base case required	Loop condition required

Quick Sort

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + mid + quick_sort(right)

Quicksort as a recursive application

Quicksort demonstrates divide and conquer: choose a pivot, partition the remaining values, recursively sort the partitions, and combine the results. Balanced partitions give an average time complexity of (O(n log n)); repeatedly choosing an extreme pivot can produce (O(n^2)).

def quick_sort(values):
    if len(values) <= 1:
        return values

    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]

    return quick_sort(lower) + equal + quick_sort(higher)