Mathematical Recursion Examples in Clojure

Mathematical examples are useful because the recursive shape is visible. Factorials can be written as a stack-safe loop/recur; permutations, combinations, and Towers of Hanoi are naturally recursive because each step reduces the problem to smaller cases.

Understanding Recursion in Clojure

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. In Clojure, use recursion when it makes the problem shape clearer; use reduce, sequence functions, or loop/recur when the problem is mostly linear iteration.

Tail Recursion and the recur Keyword

Clojure does not optimize arbitrary recursive calls. The recur keyword performs an explicit stack-safe jump when it appears in a valid tail position.

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 calculates the factorial of a number using loop and recur, so the loop can run without growing the stack.

Solving Permutations

Permutations involve rearranging elements of a set in all possible orders. Recursively generating permutations can be elegantly expressed in Clojure.

Recursive Permutation Function

Let’s define a function to generate permutations of a list:

1(defn permutations [coll]
2  (if (empty? coll)
3    '(())
4    (for [x coll
5          perm (permutations (remove #{x} coll))]
6      (cons x perm))))

Explanation:

• Base Case: If the collection is empty, return a list containing an empty list.
• Recursive Case: For each element x in the collection, remove x and recursively find permutations of the remaining elements. Prepend x to each permutation.

Comparing with Java

In Java, generating permutations typically involves more boilerplate code, often using loops and mutable data structures. Clojure’s recursive approach is more concise and expressive.

 1// Java example for generating permutations
 2public static List<List<Integer>> permutations(List<Integer> list) {
 3    if (list.isEmpty()) {
 4        List<List<Integer>> result = new ArrayList<>();
 5        result.add(new ArrayList<>());
 6        return result;
 7    }
 8    List<List<Integer>> result = new ArrayList<>();
 9    for (int i = 0; i < list.size(); i++) {
10        List<Integer> remaining = new ArrayList<>(list);
11        Integer element = remaining.remove(i);
12        for (List<Integer> perm : permutations(remaining)) {
13            perm.add(0, element);
14            result.add(perm);
15        }
16    }
17    return result;
18}

Solving Combinations

Combinations involve selecting elements from a set without regard to order. Recursive solutions can efficiently generate combinations.

Recursive Combination Function

Here’s a function to generate combinations of a given size:

1(defn combinations [coll k]
2  (cond
3    (zero? k) '(())
4    (empty? coll) '()
5    :else (let [[x & xs] coll]
6            (concat
7              (map #(cons x %) (combinations xs (dec k)))
8              (combinations xs k)))))

Explanation:

• Base Cases: Return a list containing an empty list if k is zero. Return an empty list if the collection is empty.
• Recursive Case: Use the first element x and recursively find combinations of size k-1 from the rest of the collection. Also, find combinations of size k without x.

Comparing with Java

Java solutions for combinations often involve nested loops and manual management of indices, making Clojure’s recursive approach more intuitive.

 1// Java example for generating combinations
 2public static List<List<Integer>> combinations(List<Integer> list, int k) {
 3    List<List<Integer>> result = new ArrayList<>();
 4    if (k == 0) {
 5        result.add(new ArrayList<>());
 6        return result;
 7    }
 8    if (list.isEmpty()) {
 9        return result;
10    }
11    Integer first = list.get(0);
12    List<Integer> rest = list.subList(1, list.size());
13    for (List<Integer> comb : combinations(rest, k - 1)) {
14        List<Integer> newComb = new ArrayList<>(comb);
15        newComb.add(0, first);
16        result.add(newComb);
17    }
18    result.addAll(combinations(rest, k));
19    return result;
20}

Solving the Towers of Hanoi

The Towers of Hanoi is a classic problem that demonstrates the power of recursion. The goal is to move a stack of disks from one peg to another, following specific rules.

Recursive Solution for Towers of Hanoi

Here’s a Clojure function to solve the Towers of Hanoi problem:

1(defn towers-of-hanoi [n source target auxiliary]
2  (when (pos? n)
3    (towers-of-hanoi (dec n) source auxiliary target)
4    (println "Move disk from" source "to" target)
5    (towers-of-hanoi (dec n) auxiliary target source)))

Explanation:

• Base Case: If n is zero, do nothing.
• Recursive Case: Move n-1 disks from the source to the auxiliary peg, move the nth disk to the target peg, and finally move the n-1 disks from the auxiliary to the target peg.

Comparing with Java

Java can also solve Towers of Hanoi recursively, but Clojure’s data-oriented style keeps the recursive decomposition compact.

1// Java example for solving Towers of Hanoi
2public static void towersOfHanoi(int n, char source, char target, char auxiliary) {
3    if (n > 0) {
4        towersOfHanoi(n - 1, source, auxiliary, target);
5        System.out.println("Move disk from " + source + " to " + target);
6        towersOfHanoi(n - 1, auxiliary, target, source);
7    }
8}

Try It Yourself

To deepen your understanding, try modifying the provided Clojure functions:

• Permutations: Modify the permutations function to handle duplicate elements.
• Combinations: Extend the combinations function to return combinations with repetition.
• Towers of Hanoi: Add a counter to track the number of moves made.

Visualizing Recursion with Diagrams

Let’s visualize the recursive process of solving the Towers of Hanoi using a flowchart:

    flowchart TD
	    A[Start] --> B{n > 0?}
	    B -- Yes --> C[Move n-1 disks from Source to Auxiliary]
	    C --> D[Move nth disk from Source to Target]
	    D --> E[Move n-1 disks from Auxiliary to Target]
	    E --> F[End]
	    B -- No --> F

Diagram Explanation: This flowchart illustrates the recursive steps involved in solving the Towers of Hanoi problem. The process involves moving n-1 disks, transferring the nth disk, and then moving the n-1 disks again.

Key Takeaways

• Recursion in Clojure is useful when a mathematical problem naturally decomposes into smaller cases.
• Tail-position recur makes loop-shaped mathematical examples stack-safe.
• Permutations and combinations can be elegantly expressed using recursive functions, contrasting with Java’s iterative approaches.
• Towers of Hanoi demonstrates the elegance of recursion, simplifying complex problem-solving.

Exercises

1. Permutations with Duplicates: Modify the permutations function to handle lists with duplicate elements.
2. Combinations with Repetition: Extend the combinations function to allow repeated elements in combinations.
3. Towers of Hanoi with Move Counter: Add a counter to the towers-of-hanoi function to track the number of moves.

By exploring these exercises, you’ll gain a deeper understanding of recursion and its applications in solving mathematical problems with Clojure.

Quiz: Mathematical Recursion in Clojure

By mastering recursion in Clojure, you’ll be well-equipped to tackle a wide range of mathematical problems with elegance and efficiency.