13. Recursion

1. Introduction to Recursion

Recursion is a problem‑solving technique where a function calls itself to solve smaller instances of the same problem. It mirrors many mathematical definitions, such as the factorial and Fibonacci sequences, and provides an elegant way to express algorithms that have a natural self‑similar structure.

Advantages: concise and readable code, direct mapping to mathematical definitions, ease of implementing divide‑and‑conquer strategies.

Disadvantages: function‑call overhead, risk of stack overflow if depth is too large, and potential for repeated work (e.g., naïve Fibonacci).

2. Recursive Thinking

To think recursively, identify the problem’s self‑similar part and express the solution in terms of one or more smaller sub‑problems.

1. Determine the base case that stops the recursion.
2. Define the recursive case that reduces the problem size.
3. Combine the results of the recursive calls to obtain the final answer.

Example: Factorial

The factorial of a non‑negative integer n is defined as:

• Base case: factorial(0) = 1
• Recursive case: factorial(n) = n * factorial(n‑1) for n > 0

In code:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Example: Sum of First n Natural Numbers

Similarly, the sum S(n) can be expressed as:

• Base case: S(0) = 0
• Recursive case: S(n) = n + S(n‑1)

3. Recursion Tree

A recursion tree visualises each function call as a node; its children represent the subcalls invoked by that node. The tree’s height equals the recursion depth, and the total work is the sum of the work performed at all nodes.

This representation is especially useful for analysing time complexity. For a recurrence of the form T(n) = a·T(n/b) + f(n), each level of the tree contributes a^i · f(n/b^i) work, and summing over all levels yields the overall complexity.

Example: Merge Sort Recursion Tree

Merge sort divides an array of size n into two halves, recursively sorts each half, and then merges the results in linear time.

• Root node: cost O(n) for merging.
• Two children: each processes n/2 elements, each with merge cost O(n/2) → total O(n) for the level.
• There are ⌊log₂ n⌋ + 1 levels.
• Total work: O(n) * log₂ n = O(n log n).

4. Tail Recursion

A recursive function is tail‑recursive when the recursive call is the very last operation performed; no further computation occurs after the call returns. This property enables many compilers or interpreters to optimise the recursion into an iterative loop, achieving O(1) stack space (tail‑call elimination).

Tail‑Recursive Factorial

By introducing an accumulator that carries the intermediate product, the multiplication is moved before the recursive call:

def fact_tail(n, acc=1):
    if n == 0:
        return acc
    else:
        return fact_tail(n-1, n*acc)

Here the recursive call fact_tail(n-1, n*acc) is the final action, making the function tail‑recursive.

Non‑Tail Example: Standard Factorial

The naïve version:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)  # multiplication after the call

Because the multiplication occurs after the recursive return, the call is not in tail position and cannot be directly optimised.

5. Divide and Conquer

Divide and conquer is a paradigm that breaks a problem into smaller sub‑problems, solves each recursively, and then combines the solutions. Its general recurrence is:

T(n) = a·T(n/b) + f(n)

• a = number of sub‑problems.
• b = factor by which the problem size is reduced.
• f(n) = cost of dividing the problem and merging the results.

The Master Theorem provides asymptotic solutions for recurrences of this form.

Classic Examples

6. Practical Examples

6.1 Factorial (Iterative vs Recursive)

Iterative version:

def factorial_iter(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

Recursive version (as shown earlier) mirrors the mathematical definition but incurs call‑stack overhead.

6.2 Fibonacci Sequence

Naïve recursion:

• Base cases: F(0) = 0, F(1) = 1
• Recursive case: F(n) = F(n‑1) + F(n‑2)

This leads to exponential time Θ(φⁿ) (where φ ≈ 1.618) because the same sub‑problems are recomputed many times.

Memoised recursion (top‑down DP) stores previously computed values:

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Now each F(k) is computed once, yielding Θ(n) time and Θ(n) space.

6.3 Tower of Hanoi

The classic puzzle asks to move n disks from peg A to peg C using peg B as auxiliary, obeying the rule that a larger disk may never be placed on a smaller one.

Recursive solution:

1. Move n‑1 disks from A to B (using C as auxiliary).
2. Move the largest disk from A to C.
3. Move the n‑1 disks from B to C (using A as auxiliary).

Recurrence: T(n) = 2·T(n‑1) + 1, with T(1) = 1. Solving gives T(n) = 2ⁿ – 1 moves.

6.4 File System Traversal

Listing all files in a directory tree naturally fits recursion:

import os
def listdir(path):
    for entry in os.listdir(path):
        full = os.path.join(path, entry)
        if os.path.isdir(full):
            listdir(full)          # recurse into subdirectory
        else:
            print(full)            # output file path

Each call processes one directory level; the recursion depth equals the maximum nesting of folders.

6.5 Greatest Common Divisor (Euclid’s Algorithm)

The recursive formulation is both concise and efficient:

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

The algorithm runs in O(log min(a,b)) time.

6.6 Palindrome Check

A string is a palindrome if it reads the same forward and backward. A recursive check compares the outermost characters and recurses on the substring:

def is_pal(s, l, r):
    if l >= r:
        return True
    if s[l] != s[r]:
        return False
    return is_pal(s, l+1, r-1)

Initial call: is_pal(s, 0, len(s)-1). The procedure runs in Θ(n) time and Θ(n) stack space (can be made tail‑recursive with an accumulator if desired).

7. Summary

Recursion provides a powerful and expressive tool for algorithm design, especially when the problem exhibits self‑similarity. Understanding how to formulate base and recursive cases, visualise call trees, identify tail‑recursive forms, and apply divide‑and‑conquer recurrences enables programmers to write correct, efficient, and readable code. The examples covered—factorial, Fibonacci, Tower of Hanoi, file‑system traversal, GCD, and palindrome checking—illustrate both the elegance and the pitfalls (such as exponential blow‑up or stack overflow) that must be managed through techniques like memoisation, tail‑call optimisation, or iterative conversion.