Writing Recursive Functions in Clojure

Recursive functions solve a problem by reducing it to a smaller version of the same problem. Java developers usually reach for recursion with trees, parsers, and divide-and-conquer algorithms; in Clojure, recursion is still useful, but it competes with sequence functions, reduce, loop, and recur.

The skill is not “use recursion everywhere.” The skill is recognizing when an explicit recursive shape is clearer than a collection pipeline, and when the recursive call must be made stack-safe.

Understanding Recursion in Clojure

Recursion in Clojure is a natural fit due to its functional programming paradigm. Unlike Java, which often uses iterative loops, Clojure encourages recursive solutions that align with its immutable data structures. Let’s start by examining the basic structure of a recursive function in Clojure.

Basic Structure of a Recursive Function

A recursive function typically consists of two parts:

1. Base Case: The condition under which the recursion stops.
2. Recursive Case: The part of the function where it calls itself with modified arguments.

Use ordinary self-calls for naturally shallow recursion, such as walking a small tree. Use recur only when the recursive step is in tail position and the function may run for many iterations.

Example 1: Calculating Factorials

Let’s begin with a classic example: calculating the factorial of a number. In Java, you might write a recursive factorial function like this:

1public class Factorial {
2    public static int factorial(int n) {
3        if (n <= 1) return 1;
4        return n * factorial(n - 1);
5    }
6}

In Clojure, the equivalent recursive function can be written as follows:

1(defn factorial [n]
2  (if (<= n 1)
3    1
4    (* n (factorial (dec n)))))

Explanation:

• Base Case: When n is less than or equal to 1, return 1.
• Recursive Case: Multiply n by the factorial of n-1.

Tail Recursion with recur

Clojure provides recur for recursive jumps that are already in tail position. This matters when the function might process thousands of values because recur reuses the current function or loop frame instead of adding another stack frame.

Here’s how you can rewrite the factorial function using recur:

1(defn factorial [n]
2  (let [fact-helper (fn [n acc]
3                      (if (<= n 1)
4                        acc
5                        (recur (dec n) (* n acc))))]
6    (fact-helper n 1)))

Explanation:

• Helper Function: fact-helper is a local function that carries an accumulator acc.
• Base Case: When n is less than or equal to 1, return the accumulator.
• Recursive Case: Call recur with n-1 and the updated accumulator.

Example 2: Fibonacci Numbers

The Fibonacci sequence is another classic example of recursion. In Java, a simple recursive Fibonacci function might look like this:

1public class Fibonacci {
2    public static int fibonacci(int n) {
3        if (n <= 1) return n;
4        return fibonacci(n - 1) + fibonacci(n - 2);
5    }
6}

In Clojure, the recursive Fibonacci function can be written as:

1(defn fibonacci [n]
2  (if (<= n 1)
3    n
4    (+ (fibonacci (- n 1))
5       (fibonacci (- n 2)))))

Explanation:

• Base Case: When n is 0 or 1, return n.
• Recursive Case: Sum the results of fibonacci(n-1) and fibonacci(n-2).

Optimizing Fibonacci with recur

The naive recursive approach to Fibonacci is inefficient due to repeated calculations. We can optimize it using recur:

1(defn fibonacci [n]
2  (let [fib-helper (fn [a b n]
3                     (if (zero? n)
4                       a
5                       (recur b (+ a b) (dec n))))]
6    (fib-helper 0 1 n)))

Explanation:

• Helper Function: fib-helper uses two accumulators, a and b, to store the last two Fibonacci numbers.
• Base Case: When n is 0, return a.
• Recursive Case: Call recur with updated accumulators.

Example 3: Tree Traversal

Recursion is particularly useful for traversing tree structures. Let’s consider a simple binary tree traversal. In Java, you might write a recursive method to traverse a binary tree in-order:

 1class Node {
 2    int value;
 3    Node left, right;
 4
 5    Node(int value) {
 6        this.value = value;
 7        left = right = null;
 8    }
 9}
10
11public class BinaryTree {
12    Node root;
13
14    void inOrder(Node node) {
15        if (node == null) return;
16        inOrder(node.left);
17        System.out.print(node.value + " ");
18        inOrder(node.right);
19    }
20}

In Clojure, we can represent a binary tree as nested maps and write a recursive function to traverse it:

1(defn in-order [tree]
2  (when tree
3    (concat (in-order (:left tree))
4            [(:value tree)]
5            (in-order (:right tree)))))

Explanation:

• Base Case: When the tree is nil, return an empty list.
• Recursive Case: Concatenate the results of traversing the left subtree, the root value, and the right subtree.

Visualizing Recursion with Diagrams

To better understand how recursion works, let’s visualize the recursive process using a flowchart. Below is a diagram illustrating the flow of the factorial function:

    graph TD;
	    A[Start] --> B{n <= 1?};
	    B -- Yes --> C[Return 1];
	    B -- No --> D["Calculate n * factorial(n-1)"];
	    D --> B;

Diagram Explanation: This flowchart shows the decision-making process in the recursive factorial function, highlighting the base and recursive cases.

Try It Yourself

Now that we’ve explored recursive functions, try modifying the examples:

• Factorial: Implement a version that calculates the factorial of a number using iteration instead of recursion.
• Fibonacci: Modify the Fibonacci function to return a sequence of Fibonacci numbers up to n.
• Tree Traversal: Extend the tree traversal function to perform pre-order and post-order traversals.

Exercises

1. Write a Recursive Function: Implement a recursive function in Clojure to calculate the sum of all elements in a list.
2. Optimize with recur: Rewrite the sum function using recur to make it tail-recursive.
3. Tree Depth: Write a recursive function to calculate the depth of a binary tree.

Key Takeaways

• Recursion in Clojure: Emphasizes immutability and functional programming principles.
• Stack-safe recursion: Use recur for tail-position recursive steps that might otherwise overflow the call stack.
• Practical Applications: Recursive functions are ideal for problems like factorials, Fibonacci numbers, and tree traversal.

For Java developers, recursive Clojure should feel less like replacing every for loop and more like choosing the clearest control shape. Use direct recursion for recursive data, recur for tail-position iteration, and collection functions when the problem is just transforming or reducing values.

Further Reading

• Official Clojure Documentation
• ClojureDocs
• Functional Programming in Clojure

Quiz: Recursive Functions in Clojure