Implementing Recursive Algorithms in Clojure

Java developers usually learn algorithms with arrays, indexes, and in-place updates. Clojure can express many of the same algorithms with immutable collections, recursive decomposition, and higher-order functions. The goal is not to make every algorithm recursive; it is to choose the clearest shape for the data and performance constraints.

Understanding Recursion in Clojure

Before diving into specific algorithms, separate three ideas: direct recursion for recursive data, loop/recur for long linear state transitions, and sequence functions such as map, filter, and reduce for collection processing.

Tail Recursion and recur

Tail recursion is a form of recursion where the recursive step is the final operation. In Clojure, the stack-safe version is written explicitly with recur, which reuses the current function or loop frame.

1(defn factorial [n]
2  (loop [acc 1, n n]
3    (if (zero? n)
4      acc
5      (recur (* acc n) (dec n)))))

In this example, factorial uses loop and recur to compute the factorial of a number without growing the stack, similar to a loop in Java.

Implementing Quicksort

Quicksort is a classic divide-and-conquer algorithm that sorts by partitioning an array into two sub-arrays, then recursively sorting the sub-arrays.

Quicksort in Java

Here’s a typical implementation of quicksort in Java:

 1public class QuickSort {
 2    public static void quickSort(int[] array, int low, int high) {
 3        if (low < high) {
 4            int pi = partition(array, low, high);
 5            quickSort(array, low, pi - 1);
 6            quickSort(array, pi + 1, high);
 7        }
 8    }
 9
10    private static int partition(int[] array, int low, int high) {
11        int pivot = array[high];
12        int i = (low - 1);
13        for (int j = low; j < high; j++) {
14            if (array[j] <= pivot) {
15                i++;
16                int temp = array[i];
17                array[i] = array[j];
18                array[j] = temp;
19            }
20        }
21        int temp = array[i + 1];
22        array[i + 1] = array[high];
23        array[high] = temp;
24        return i + 1;
25    }
26}

Quicksort in Clojure

In Clojure, we can implement quicksort using recursion and immutable data structures:

1(defn quicksort [coll]
2  (if (empty? coll)
3    coll
4    (let [pivot (first coll)
5          rest (rest coll)
6          less (filter #(<= % pivot) rest)
7          greater (filter #(> % pivot) rest)]
8      (concat (quicksort less) [pivot] (quicksort greater)))))

Explanation:

• Base Case: If the collection is empty, return it.
• Recursive Case: Choose a pivot (first element), partition the rest into less and greater sub-collections, and recursively sort them.

Diagram: Quicksort Flow

    flowchart TD
	    A[Start] --> B{Is collection empty?}
	    B -- Yes --> C[Return collection]
	    B -- No --> D[Choose pivot]
	    D --> E[Partition into less and greater]
	    E --> F[Recursively sort less]
	    E --> G[Recursively sort greater]
	    F --> H[Concatenate results]
	    G --> H
	    H --> I[Return sorted collection]

This diagram illustrates the recursive flow of the quicksort algorithm in Clojure.

Implementing Mergesort

Mergesort is another divide-and-conquer algorithm that divides the array into halves, sorts them, and merges the sorted halves.

Mergesort in Java

Here’s how mergesort might look in Java:

 1public class MergeSort {
 2    public static void mergeSort(int[] array, int left, int right) {
 3        if (left < right) {
 4            int middle = (left + right) / 2;
 5            mergeSort(array, left, middle);
 6            mergeSort(array, middle + 1, right);
 7            merge(array, left, middle, right);
 8        }
 9    }
10
11    private static void merge(int[] array, int left, int middle, int right) {
12        int n1 = middle - left + 1;
13        int n2 = right - middle;
14        int[] L = new int[n1];
15        int[] R = new int[n2];
16        for (int i = 0; i < n1; ++i)
17            L[i] = array[left + i];
18        for (int j = 0; j < n2; ++j)
19            R[j] = array[middle + 1 + j];
20        int i = 0, j = 0;
21        int k = left;
22        while (i < n1 && j < n2) {
23            if (L[i] <= R[j]) {
24                array[k] = L[i];
25                i++;
26            } else {
27                array[k] = R[j];
28                j++;
29            }
30            k++;
31        }
32        while (i < n1) {
33            array[k] = L[i];
34            i++;
35            k++;
36        }
37        while (j < n2) {
38            array[k] = R[j];
39            j++;
40            k++;
41        }
42    }
43}

Mergesort in Clojure

In Clojure, mergesort can be implemented using recursion and higher-order functions:

 1(defn merge [left right]
 2  (cond
 3    (empty? left) right
 4    (empty? right) left
 5    :else (let [l (first left)
 6                r (first right)]
 7            (if (<= l r)
 8              (cons l (merge (rest left) right))
 9              (cons r (merge left (rest right)))))))
10
11(defn mergesort [coll]
12  (if (<= (count coll) 1)
13    coll
14    (let [mid (quot (count coll) 2)
15          left (subvec coll 0 mid)
16          right (subvec coll mid)]
17      (merge (mergesort left) (mergesort right)))))

Explanation:

• Base Case: If the collection has one or zero elements, it’s already sorted.
• Recursive Case: Split the collection into two halves, recursively sort each half, and merge the sorted halves.

Diagram: Mergesort Flow

    flowchart TD
	    A[Start] --> B{Is collection size <= 1?}
	    B -- Yes --> C[Return collection]
	    B -- No --> D[Split into left and right]
	    D --> E[Recursively sort left]
	    D --> F[Recursively sort right]
	    E --> G[Merge sorted halves]
	    F --> G
	    G --> H[Return sorted collection]

This diagram shows the recursive flow of the mergesort algorithm in Clojure.

Traversing Data Structures

Traversing data structures is a common task in algorithm implementation. In Clojure, recursion and higher-order functions like map, reduce, and filter are often used for this purpose.

Traversing a Binary Tree

Let’s implement a simple binary tree traversal in Clojure.

 1(defn inorder-traversal [tree]
 2  (when tree
 3    (concat (inorder-traversal (:left tree))
 4            [(:value tree)]
 5            (inorder-traversal (:right tree)))))
 6
 7;; Example usage
 8(def tree {:value 1
 9           :left {:value 2
10                  :left nil
11                  :right nil}
12           :right {:value 3
13                   :left nil
14                   :right nil}})
15
16(inorder-traversal tree) ;; => (2 1 3)

Explanation:

• Base Case: If the tree is nil, return an empty list.
• Recursive Case: Traverse the left subtree, visit the root, and traverse the right subtree.

Diagram: Inorder Traversal

    flowchart TD
	    A[Start] --> B{Is tree nil?}
	    B -- Yes --> C[Return empty list]
	    B -- No --> D[Traverse left subtree]
	    D --> E[Visit root]
	    E --> F[Traverse right subtree]
	    F --> G[Concatenate results]
	    G --> H[Return traversal list]

This diagram illustrates the recursive flow of an inorder traversal in a binary tree.

Try It Yourself

To deepen your understanding, try modifying the code examples:

• Quicksort: Change the pivot selection strategy and observe how it affects performance.
• Mergesort: Implement a bottom-up iterative version using loop and recur.
• Tree Traversal: Implement preorder and postorder traversals.

Exercises

1. Implement a Recursive Fibonacci Function: Write a recursive function to compute Fibonacci numbers and optimize it using memoization.
2. Binary Search: Implement a recursive binary search algorithm for a sorted vector.
3. Graph Traversal: Implement depth-first and breadth-first search algorithms for a graph represented as an adjacency list.

Key Takeaways

• Recursion is a powerful tool when the problem decomposes into smaller instances of the same shape.
• Immutable Data Structures in Clojure lead to different algorithmic approaches compared to Java.
• Higher-Order Functions like map, reduce, and filter simplify data structure traversal.
• Tail-position recur makes long linear loops stack-safe without implying automatic optimization of ordinary recursive calls.

By exploring these algorithms in Clojure, you gain a deeper understanding of functional programming paradigms and how they can be applied to solve complex problems efficiently. Now, let’s apply these concepts to manage state effectively in your applications.

For further reading, check out the Official Clojure Documentation and ClojureDocs.

Quiz: Recursive Algorithms in Clojure