Recursion

Overview

Recursion is a programming technique where a function calls itself to solve smaller subproblems of the original problem. It is commonly used in divide-and-conquer algorithms, backtracking, tree traversals, and more.

In Swift, recursive functions are straightforward to write, but they must be carefully managed to avoid stack overflow or inefficiency due to repeated work.

Key Concepts

Base Case: The condition that stops recursion.
Recursive Case: The part of the function where it calls itself.
Call Stack: Each recursive call is added to the call stack until the base case is reached.

Factorial Example

The factorial of a number n is defined as:

n! = n × (n - 1)!

With base case: 0! = 1

func factorial(_ n: Int) -> Int {
    if n == 0 {
        return 1
    }
    return n * factorial(n - 1)
}

Fibonacci Example

Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, ...

func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

Tree Traversal (Binary Tree)

class TreeNode {
    var value: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ value: Int) {
        self.value = value
    }
}

func inOrderTraversal(_ node: TreeNode?) {
    guard let node = node else { return }
    inOrderTraversal(node.left)
    print(node.value)
    inOrderTraversal(node.right)
}

Backtracking Example (N-Queens)

func solveNQueens(_ n: Int) -> [[String]] {
    var board = Array(repeating: Array(repeating: ".", count: n), count: n)
    var results: [[String]] = []

    func isValid(_ row: Int, _ col: Int) -> Bool {
        for i in 0..<row {
            if board[i][col] == "Q" ||
               (col - row + i >= 0 && board[i][col - row + i] == "Q") ||
               (col + row - i < n && board[i][col + row - i] == "Q") {
                return false
            }
        }
        return true
    }

    func backtrack(_ row: Int) {
        if row == n {
            results.append(board.map { $0.joined() })
            return
        }

        for col in 0..<n {
            if isValid(row, col) {
                board[row][col] = "Q"
                backtrack(row + 1)
                board[row][col] = "."
            }
        }
    }

    backtrack(0)
    return results
}

When to Use Recursion

Problems with overlapping subproblems (use memoization).
Data structures with recursive nature (e.g., trees, graphs).
Backtracking problems (e.g., permutations, combinations).
Divide and conquer algorithms (e.g., merge sort, quick sort).

Tips for Writing Recursive Functions

Always define a clear base case to prevent infinite recursion.
Consider memoization for optimization.
Convert to iteration if recursion depth is too deep.
Be cautious of stack overflow on large input sizes.

Summary

Recursion is a powerful tool in Swift for solving problems that can be broken down into smaller, similar problems. Mastering recursion helps you approach complex algorithms with elegance and clarity.