Chapter 5 — Recursion

What is recursion?
Recursion is a method where a problem is solved by expressing its solution in terms of solutions to smaller instances of the same problem. In programming, a recursive function calls itself, directly or indirectly, until it reaches a base case that can be answered without further recursion.

Why recursion is useful
Many problems have naturally self-similar structure: mathematical definitions (factorial, Fibonacci), hierarchical data (trees), and combinatorial generation (permutations, subsets). Recursion allows code that mirrors these definitions and often produces clearer, shorter implementations than iterative alternatives. The key is to find how a problem of size n can be reduced to one or more problems of smaller size.

Essential components
Every recursive function must have at least two parts: the base case and the recursive case. The base case handles the simplest inputs (for example, empty list or n=0) and returns a concrete result. The recursive case reduces the input towards the base case and combines results of recursive calls to compute the final answer. A correct reduction ensures progress: some measure (like n) strictly decreases on each call to guarantee termination.

Execution behaviour
Each call to a recursive function creates a new activation record on the program stack that stores parameters, local variables and return address. When a call returns, control comes back to the caller which may then continue work. Because of this stacking, recursion uses additional memory proportional to call depth and may cause stack overflow for very deep recursion.

Kinds of recursion
Linear recursion: each call makes one recursive call (e.g., factorial). Tree recursion: calls make multiple recursive calls (e.g., naive Fibonacci). Tail recursion: recursive call is final step so some compilers can reuse frames. Divide-and-conquer: split input into parts, solve each recursively and combine results (e.g., merge sort).

Practical concerns
Recursion offers clarity but may cost extra function-call overhead and stack space. Avoid naive recursion that repeats work; use memoization or iterative methods when required for performance. Test recursive functions with small inputs and draw call trees to verify correctness and termination.

Overview
Writing a correct recursive function requires careful selection of base cases and precise reduction steps for the recursive case. The base case provides the stopping condition and a direct answer; the recursive case defines how the problem is reduced. Clear design prevents infinite recursion and ensures correctness.

Choosing base cases
Identify the simplest inputs that you can answer without recursion: empty structures (empty list, null node), minimal integers (0 or 1), or trivial conditions (start index beyond end). Some functions require more than one base case (for example, Fibonacci uses n==0 and n==1). Ensure base cases cover all situations where recursion must stop, including malformed input if the function must handle it.

Reduction and progress measure
Design your recursive step so that at least one parameter decreases according to a well-founded measure (typically a non-negative integer). Document which parameter serves as the measure. For arrays, use index ranges; for lists, use the tail; for trees, recursive calls use child nodes. Showing that the measure strictly decreases in every recursive call proves termination.

Combining results
When the recursive call(s) return results, you must combine them with current data to produce the correct final result. The combine operation depends on problem type: multiplication for factorial, addition for sums, concatenation for list building, merge for merge sort, or selecting max/min for some divide-and-conquer tasks.

Use helper functions
Helper functions let you add parameters like indices, accumulators or visited markers without complicating the public interface. For example, computing the sum of first n elements is simpler with a helper that carries the current index. Helper functions also allow tail-recursive transformations to improve space use when supported by the runtime.

Side effects and backtracking
If recursion modifies shared state (like marking visited nodes or swapping array elements), always restore state before returning (backtrack). Failure to undo changes causes incorrect results in later branches. Use local copies or explicit undo steps to keep logic clear.

Testing and tracing
Before coding, trace the algorithm on small inputs and draw the call tree. Test base cases and edge cases (empty input, single element, maximum allowed sizes). Add assertions or logs in development to verify that the base case is reached and that parameters change as expected.

Conceptual difference
Iteration repeats statements using loops (for, while) while recursion solves problems by self-calls. Both can implement many algorithms, but their strengths differ. Iteration explicitly manages loop variables and termination conditions. Recursion expresses self-similar problems naturally and often maps directly to mathematical definitions or hierarchical structures.

Readability and problem fit
Recursion often yields shorter, clearer code when a problem is naturally defined in terms of smaller subproblems: tree traversals, combinations, or divide-and-conquer algorithms. Iteration can become awkward for such tasks, requiring explicit stacks or complex loop structures. For problems like factorial, both are simple; for tree traversals, recursion is typically the straightforward choice.

Performance and resource use
Each recursive call has overhead: pushing a stack frame, storing parameters and local variables, and returning. This adds constant factor overhead per call and consumes stack memory proportional to recursion depth. Iterative code usually uses constant extra space and avoids function-call overhead. For linear-depth recursion (depth O(n)), iterative solutions may be preferable to avoid stack overflow.

Converting recursion to iteration
When converting complex recursion (especially tree recursion) to iteration, you simulate the call stack with an explicit stack data structure. For tail-recursive functions, many compilers can optimize into iteration automatically (tail-call optimization). For multiple recursive calls, conversion requires a more involved explicit stack or restructured algorithm.

Time complexity comparison
Time complexity of equivalent recursive and iterative algorithms is often the same asymptotically. However, naive recursion may recompute overlapping subproblems and thus be asymptotically worse; memoization or dynamic programming remedies this. When converting to iteration, ensure you do not lose clarity or introduce more complex control flow than necessary.

Choosing which to use
Prefer recursion when it simplifies reasoning, mirrors problem structure, or eases correctness proofs. Prefer iteration when performance constraints, limited stack, or predictable memory usage are critical. In practical systems, combine both: use recursion for conceptual clarity and transform to iteration where performance or stack limits demand it.

Why induction and recursion are related
Recursive functions define results in terms of smaller inputs; mathematical induction proves properties for all natural numbers by assuming the property holds for smaller numbers and proving it for the next. This alignment makes induction the standard technique to prove correctness of recursive algorithms.

Structure of an induction proof
Two main steps: base case and inductive step. Base case: prove the algorithm gives the correct result for minimal inputs (often n=0 or n=1). Inductive step: assume the algorithm works for all inputs smaller than n (induction hypothesis) and show it then works for n by using that the algorithm uses results of smaller inputs which by hypothesis are correct.

Strong vs simple induction
Simple (weak) induction assumes correctness for n-1 to prove for n and suffices for linear recursions. Strong induction assumes correctness for all values less than n and is useful when the recursive step depends on multiple smaller values (e.g., Fibonacci uses n-1 and n-2). Choose the form matching the recursion.

Proving termination
A correctness proof must also show termination: there must be a well-founded measure (like n) that strictly decreases with every recursive call, ensuring eventual reach of a base case. For multiple calls, show each call reduces the measure. This prevents infinite recursion and guarantees the algorithm completes.

Using induction in complex algorithms
For divide-and-conquer algorithms prove that combining correct results from subcalls yields the correct overall result. For backtracking, show that the search explores all valid candidates and that pruning conditions only exclude impossible candidates. For dynamic programming, prove that the order of computation respects dependencies so stored values are correct when used.

Writing the proof
In exams and assignments, present base case(s) clearly, state the induction hypothesis, and demonstrate the inductive step by substituting correct values returned by recursive calls. Conclude by noting termination based on the measure. This concise structure demonstrates rigorous understanding at ISC level.

Recurrences and their meaning
When an algorithm calls itself on smaller inputs, its running time T(n) is often described by a recurrence relation expressing T(n) in terms of T for smaller sizes plus extra non-recursive work. Solving these recurrences gives asymptotic time complexity. Typical recurrences include T(n)=T(n-1)+O(1) for linear recursion, T(n)=T(n/2)+O(1) for binary search, and T(n)=aT(n/b)+f(n) for many divide-and-conquer algorithms.

Methods to solve recurrences
Common techniques: substitution (guess and verify), recursion tree (draw the calls and sum costs level by level), and the Master Theorem (for T(n)=aT(n/b)+f(n) with constants a>=1, b>1). Use the method that fits the recurrence form most naturally.

Recursion tree technique
A recursion tree visualises each call as a node labelled with its non-recursive cost. The tree shows how many calls exist at each depth and the cost per call. Summing costs across levels gives the total. For balanced divide-and-conquer, the tree often has logarithmic height and geometric number of nodes per level.

Master Theorem summary
For T(n)=aT(n/b)+f(n), compare f(n) with n^{log_b a}. If f(n) is asymptotically smaller, equal (with log factor), or larger, T(n) falls into case 1, 2 or 3 respectively, producing O(n^{log_b a}), O(n^{log_b a} log n), or O(f(n)). Apply conditions carefully (regularity condition for case 3).

Space complexity and recursion depth
Recursive algorithms use stack space proportional to recursion depth. For T(n)=T(n/2)+..., depth O(log n); for linear recursion depth O(n). Always report both time and extra space due to recursion in answers.

Examples
Binary search: T(n)=T(n/2)+O(1) => O(log n). Merge sort: T(n)=2T(n/2)+O(n) => O(n log n). Naive Fibonacci: T(n)=T(n-1)+T(n-2)+O(1) => exponential O(φ^n).

Practical tips
Write the recurrence for your algorithm, pick a solving method, and justify each step. For divide-and-conquer, drawing the recursion tree quickly provides intuition about costs per level and total cost, which examiners expect at ISC level.

Definition of tail recursion
A recursive call is tail-recursive when it is the last operation in the function, such that the caller has nothing to do after the call returns. In a tail-recursive function there is no pending work after the recursive call, which makes it possible for compilers or interpreters to perform tail-call optimization (TCO) and reuse the current function’s stack frame for the recursive call.

Benefits and limits
If TCO is supported by the language runtime or compiler, tail recursion eliminates linear stack growth and makes the recursion use O(1) stack space like iteration. However, not all languages or compilers perform TCO; in those environments tail recursion improves clarity but may still consume stack space. Additionally, many recursive problems with multiple recursive calls cannot be made tail-recursive without changing algorithm structure.

Transforming to tail recursion
Use accumulator parameters that carry intermediate results to the next call so no work remains after returning. For factorial, standard recursive form fact(n)=n*fact(n-1) is not tail-recursive because multiplication occurs after return. Convert to fact_tail(n, acc) where acc accumulates the product: fact_tail(0, acc)=acc; else fact_tail(n-1, n*acc). Initial call fact_tail(n,1) gives the same answer in tail-recursive style.

Other examples
Sum of first n numbers: sum(n)=n+sum(n-1) becomes sum_tail(n,acc) with sum_tail(0,acc)=acc otherwise sum_tail(n-1,acc+n). Reversing a list can be written tail-recursively by carrying a partially built output list as an accumulator.

Compiler optimizations
When TCO is present, the call frame is reused and recursion depth does not increase. Some languages (functional languages like Scheme) guarantee TCO, while many imperative languages (e.g., Java) do not. Understand your target platform when relying on tail recursion for performance.

Practical advice
Prefer tail recursion when you want recursive clarity and expect TCO; otherwise, convert to iterative loops for guaranteed constant space. Use helper functions with accumulator parameters to keep public API simple while enabling tail recursion in implementation.

Divide-and-conquer pattern
Divide-and-conquer algorithms split a problem into smaller subproblems, solve them recursively, and combine their results. Typical steps: divide, recurse, combine. Well-known examples are merge sort and quick sort. The cost of the algorithm depends on how many subproblems are created, their sizes, and the cost to combine their solutions.

Using recursion trees
A recursion tree represents the calls of a divide-and-conquer algorithm as a tree where each node corresponds to a recursive call and is annotated with its non-recursive cost. The root represents the initial call of size n. Children nodes represent subcalls on portions of the input. By summing costs across each level of the tree and across all levels, you can estimate total work.

Example: merge sort
Merge sort divides into two halves and merges in linear time each level. The recursion tree has height log n, and each level does O(n) merging work, leading to total O(n log n). The recursion tree view makes it easy to see why the work multiplies across levels and how many levels exist.

Applying the Master Theorem
Many divide-and-conquer recurrences fit the form T(n)=aT(n/b)+f(n). The Master Theorem provides a quick way to solve such recurrences by comparing f(n) with n^{log_b a}. For balanced splits (equal sized subproblems) and regular combine costs, this theorem gives closed-form asymptotic bounds.

Unbalanced splits and worst cases
When splits are uneven, depth and total cost change. Quick sort worst-case arises from extremely unbalanced partitions (one side size n-1), producing O(n^2) time but average-case balanced splits give O(n log n). Analysis must consider expected splits or worst-case splits depending on problem guarantees.

Design and optimisation
When designing divide-and-conquer solutions, aim for balanced division and efficient combine steps. Use recursion trees to visualise bottlenecks, and consider tail recursion elimination or converting big combine steps into linear or sublinear work to improve asymptotic behaviour.

Factorial
Factorial n! is defined by n! = 1 for n=0 and n! = n*(n-1)! for n>0. The recursive implementation follows this definition directly and is a standard teaching example. The simple recursive version performs n multiplications and makes n+1 calls including the base case, so time complexity is O(n). The recursion depth is n, so the call stack requires O(n) space. For moderately large n the function is fine, but for very large n an iterative approach or big-integer support is needed to avoid overflow.

Tail-recursive factorial
To reduce stack usage where tail-call optimization is available, transform factorial into a tail-recursive form using an accumulator. The helper function fact_tail(n, acc) returns acc when n==0 and otherwise calls fact_tail(n-1, n*acc). The initial call fact_tail(n,1) produces the same result but leaves no pending computation after the recursive call, enabling possible frame reuse by compilers that support TCO.

Fibonacci sequence
Fibonacci numbers are defined F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2). The direct recursive translation is compact but inefficient: it recomputes the same subproblems repeatedly and has exponential time complexity approximately O(φ^n), where φ≈1.618 is the golden ratio. The naive recursion is useful to illustrate recursion trees and overlapping subproblems, but is impractical for larger n.

Optimising Fibonacci
Two effective fixes are memoization and iteration. Memoization stores computed values in an array or map so that each F(k) is computed once, converting time to O(n) and adding O(n) space for the memo table. An iterative approach computes F(n) with two variables in O(n) time and O(1) space. For very large n, fast doubling or matrix exponentiation computes Fibonacci in O(log n) time using algebraic techniques, which is beyond basic recursion but worth noting for advanced study.

Correctness and limits
Use induction to prove correctness of both recursive factorial and memoized Fibonacci. Always mention number growth and possible integer overflow in answers and consider constraints when choosing which implementation to present.

Linear search
Linear search examines each element of a collection sequentially until the target is found or the collection ends. When written recursively, the function checks the first element and, if not found, calls itself on the remainder. This yields the recurrence T(n)=T(n-1)+O(1) and time complexity O(n). The recursion depth is O(n), so recursive linear search consumes linear stack space; this makes the iterative version preferable in practice for arrays. Recursive linear search may still be a natural fit when the data structure is a list defined recursively.

Recursive implementation details
An index-based helper is a common pattern: search(a, low, high, key) where base case low>high returns not found. For list-based recursion, the base case is empty list. Ensure you return appropriate indices or sentinel values and that you avoid needless copying of sublists in each call by using indices or pointers.

Binary search
Binary search requires a sorted array. The recursive algorithm computes mid = low + (high - low)/2, compares the key with a[mid], and recurses into the left or right half. The recurrence T(n)=T(n/2)+O(1) leads to O(log n) time complexity and O(log n) recursion depth. Binary search is efficient and widely used, but careful index handling is necessary to avoid off-by-one mistakes and infinite recursion.

Edge cases and correctness
Define clearly whether high is inclusive or exclusive and keep consistent. Use low + (high - low)/2 to prevent integer overflow in some languages. Base case low>high (or low==high checks) must be established so that the recursive calls shrink the interval each time, guaranteeing termination. Prove correctness by induction on the interval size: if it works for smaller intervals then halving preserves correctness.

When to use recursion for search
Binary search is often implemented iteratively in production to avoid function-call overhead and stack use, yet the recursive form remains concise and instructive for understanding divide-and-conquer. Use recursive linear search mainly for recursive data structures such as linked lists where recursion maps directly to the data representation.

Merge sort
Merge sort is a classic stable divide-and-conquer algorithm. It splits the array into two halves, recursively sorts each half and then merges the two sorted halves into one sorted array. Splitting cost is negligible; merging two sorted subarrays of total size n takes O(n) time. The recurrence T(n)=2T(n/2)+O(n) yields O(n log n) time via recursion tree or Master Theorem. Merge sort requires O(n) auxiliary space for merging if implemented straightforwardly.

Quick sort
Quick sort selects a pivot element and partitions the array into elements less than the pivot and greater than the pivot, then recursively sorts the partitions. Partitioning takes O(n) time. If partitions are balanced on average, recurrence approximates T(n)=2T(n/2)+O(n) giving average-case O(n log n). However, worst-case (already sorted input with poor pivot) yields T(n)=T(n-1)+O(n) => O(n^2). Randomised pivot selection or median-of-three heuristic reduces chance of worst-case behavior.

Stability and space
Merge sort is stable and predictable in time but uses extra space; quick sort is usually implemented in-place and has better memory locality and lower constants in practice, which is why it is often faster on average. Quick sort uses O(log n) expected stack space, merge sort uses O(log n) recursion but O(n) extra array space for merging unless special in-place merges are used.

Practical improvements
Hybrid approaches switch to insertion sort for small subarrays to reduce overhead. Choose pivot randomly or use median-of-three to avoid pathological inputs. Tail recursion elimination can reduce stack depth in implementations that sort one side then loop to sort the other.

Which to choose?
Use merge sort when stable sort or guaranteed O(n log n) worst-case is required (e.g., external sorting). Use quick sort for general in-memory sorting where average performance and low extra memory are priorities. In exam answers, state recurrences, solve them, and mention space and stability trade-offs.

What backtracking is
Backtracking is a recursive search technique used to solve constraint satisfaction and combinatorial search problems. It builds candidate solutions incrementally, and abandons (backtracks from) a candidate as soon as it determines that this candidate cannot possibly lead to a valid complete solution. This pruning reduces the search space compared to naive exhaustive search and is effective for many puzzles and arrangement problems.

General backtracking template
The pattern of backtracking includes: check if current partial solution is complete; if so, record or return it. Otherwise, iterate through available choices; make a choice and update state; check feasibility (prune early if impossible); recurse to continue building; undo the choice before trying the next option. The undo step is essential to restore shared state for subsequent branches.

Where backtracking shines
N-Queens, Sudoku, crosswords, and constraint-based scheduling are typical problems where backtracking is effective. In N-Queens, placing one queen per row and checking column and diagonal conflicts lets the algorithm prune many placements early. In Sudoku, row/column/block constraints drastically reduce branches so backtracking finishes quickly on typical puzzles.

Pruning and heuristics
Effective backtracking uses pruning to cut branches quickly. Techniques include feasibility checks (O(1) tests using arrays or bitsets), ordering heuristics like choosing the most constrained variable first (MRV), and forward checking to eliminate choices that would make future constraints impossible. These heuristics often transform impractical brute-force into practical search.

Implementation details
Represent state compactly and provide constant-time feasibility checks where possible. For example, keep boolean arrays for columns and both diagonals in N-Queens. Always undo changes after recursion (backtrack). For problems requiring a single solution, return a boolean indicating success to stop further recursion. For enumerating all solutions, collect results in a list or stream them as they are found.

Complexity notes
Backtracking worst-case is still exponential O(b^d) where b is branching factor and d is depth, but pruning and heuristics often reduce effective branching dramatically. In exam answers, justify expected performance by describing pruning effectiveness and branch reduction.

Generating permutations
To generate permutations of n distinct elements, fix one position and recursively permute the remaining positions. A standard method swaps the element at the current index with each element at or after that index, recurses for the next index, and swaps back (backtracking) to restore the original order. This produces n! permutations. Ensure that for repeated elements you handle duplicates by checking or sorting and skipping equal swaps.

Generating subsets and combinations
Subsets (power set) can be generated by a binary choice at each element: include or exclude. Recursively process the next element with the two choices. This yields 2^n subsets. To generate combinations of k elements, track how many have been chosen and stop when k are selected; prune branches when remaining elements cannot fill remaining slots.

Complexity and output size
These generation tasks are inherently exponential in output size: permutations O(n! * n) if each permutation is output; subsets O(2^n * n). Because output size grows rapidly, these methods are feasible only for small n in practice (n ≤ 8–12 for permutations in typical problems). When asked to list all solutions, mention output complexity in answers.

Handling duplicates
When input has repeated elements, naive swapping produces duplicate permutations. To avoid duplicates, sort the array and skip swapping with an element equal to a previous one at the same recursion level, or use a boolean used[] array and build permutations by choosing unused elements in order.

Applications
Permutations and combinations appear in anagram generation, test-case creation, combinatorial enumeration tasks in competitive programming, and as subroutines in larger search problems. Use recursion with pruning to limit the search space when constraints apply.

Implementation notes
Use backtracking to restore state after recursive calls. For combinations, use start index to avoid generating same combination in different orders. For permutations, swapping in-place avoids extra arrays but requires careful backtracking.

Linked lists and recursion
Recursion suits linked lists because a list is defined as head + tail. Typical recursive operations: computing length, printing elements, summing values, searching, and reversing. For example, length(node) = 0 if node==null else 1 + length(node.next). Reversal can be done recursively by reversing the tail and adjusting pointers, but iterative reversal is often simpler and more space-efficient.

Binary trees and recursion
Trees are inherently recursive: each node has left and right subtrees that are trees too. Traversals—preorder, inorder, postorder—are most simply expressed recursively: for inorder: inorder(node.left); visit(node); inorder(node.right). Many tree algorithms use similar patterns: computing height, counting nodes, searching BSTs, and balancing operations.

Combining results
When a recursive call returns information (like height or subtree sums), combine child results to compute the parent result. Example: height(node) = 0 if null else 1 + max(height(left), height(right)). For post-order computations use children results before finalising the parent computation.

Pointer updates and state
When recursion modifies pointers or node values (e.g., deleting nodes, reversing pointers), make sure return values are used to reassign child pointers correctly. For linked list reversal, a typical recursive pattern returns the new head and updates next pointers carefully before nullifying the old head.next.

Edge cases and complexity
Always handle empty structures (null nodes) as base cases. Traversals visit each node once so time is O(n). Recursion uses O(h) stack space where h is tree height; balanced trees have h=O(log n) but skewed trees may have h=O(n). Note both time and space when analysing algorithms.

Testing and helper functions
Use helper functions to include additional parameters like parent pointers, indices, or accumulators. Test on empty, single-node and skewed structures to ensure correctness and to detect stack depth issues early. For deep structures consider iterative alternatives or tail-recursive designs where possible.

Redundant computations in recursion
Many simple recursive solutions recompute the same subproblems repeatedly. For example, naive Fibonacci recomputes F(k) many times. When the number of distinct subproblems is much smaller than the number of recursive calls, memoization avoids redundancy by storing results of computed states.

Top-down memoization
Top-down dynamic programming, or memoization, starts with a recursive formulation and stores (caches) computed results in a table (array or map) keyed by the input parameters. Before computing a state, check the table; if the value exists return it, otherwise compute, store, and return. This converts many exponential recursions into polynomial time equal to number of distinct states times cost per state.

Bottom-up dynamic programming
Bottom-up DP fills a table iteratively in an order that ensures needed subproblems are computed before dependent states. Bottom-up often uses less function-call overhead and can be more space-efficient because it allows careful ordering and possible discarding of unneeded rows of the table.

Choosing state representation
Represent states compactly to keep table size manageable. For one-parameter recurrences use 1D arrays; for two-parameter problems use 2D arrays; for combinatorial state spaces use hash maps with composite keys. Evaluate memory trade-offs: memoization reduces time but increases space to store the table.

Examples
Fibonacci with memoization becomes O(n) time and O(n) space. Computing binomial coefficients using Pascal recurrence can be implemented top-down with memo or bottom-up by filling a table. Paths in grids with obstacles are typical DP problems where memoization greatly improves performance.

Practical tips
Initialize memo table with sentinel values for uncomputed states. For multiple test cases, clear or reuse memo carefully. If only final result is required and intermediate storage can be pruned, reduce memory by storing only necessary rows (space optimization). When writing exam answers, show recurrence, indicate memoization table size and complexity after memoization.