Using recur in Clojure

recur is Clojure’s explicit way to say “jump back to this function or loop with new values.” For Java engineers, it is closest to a while loop with reassigned local variables, except the next values are passed as arguments instead of mutated in place.

Use recur when a recursive-looking algorithm is really a long linear loop. Do not treat it as general tail-call optimization for arbitrary functions.

Understanding Tail Recursion

Before diving into recur, let’s briefly discuss tail recursion. A function is tail-recursive if the recursive step is the last operation performed before the function returns. In Clojure, writing that step as recur lets the compiler reuse the current frame.

Tail Recursion in Java

In Java, tail recursion is not optimized by the JVM, which means each recursive call adds a new frame to the stack. Consider the following Java example of a factorial function:

 1public class Factorial {
 2    public static int factorial(int n) {
 3        if (n == 0) {
 4            return 1;
 5        } else {
 6            return n * factorial(n - 1);
 7        }
 8    }
 9
10    public static void main(String[] args) {
11        System.out.println(factorial(5)); // Output: 120
12    }
13}

This implementation is not tail-recursive because the multiplication operation occurs after the recursive call. As a result, the stack grows with each call, potentially leading to a stack overflow for large inputs.

Tail Recursion in Clojure with recur

Clojure addresses the loop-shaped case with recur. It can be used in place of a recursive self-call only when the step is in tail position and targets the nearest function or loop. Let’s rewrite the factorial function using recur in Clojure:

1(defn factorial [n]
2  (let [helper (fn [n acc]
3                 (if (zero? n)
4                   acc
5                   (recur (dec n) (* n acc))))]
6    (helper n 1)))
7
8(println (factorial 5)) ; Output: 120

In this example, we define a helper function within factorial that takes an accumulator acc to hold the result. recur jumps back to that helper with the decremented value of n and the updated accumulator. Because the jump is in tail position, Clojure reuses the current stack frame.

Key Characteristics of recur

• Tail Position Requirement: recur must be the last operation in a function or loop. It cannot be used in non-tail positions.
• Local Recursion: recur is limited to the current function or loop. It cannot be used to call other functions.
• Stack Frame Reuse: By reusing the current stack frame, recur prevents stack overflow, making it suitable for deep recursion.

Rewriting Recursive Functions with recur

To effectively use recur, we often need to refactor our recursive functions to ensure the recursive call is in the tail position. Let’s explore some common patterns and examples.

Example: Calculating Fibonacci Numbers

The Fibonacci sequence is a classic example of recursion. Here’s a naive recursive implementation in Java:

 1public class Fibonacci {
 2    public static int fibonacci(int n) {
 3        if (n <= 1) {
 4            return n;
 5        } else {
 6            return fibonacci(n - 1) + fibonacci(n - 2);
 7        }
 8    }
 9
10    public static void main(String[] args) {
11        System.out.println(fibonacci(5)); // Output: 5
12    }
13}

This implementation is inefficient due to repeated calculations. Let’s rewrite it in Clojure using recur:

1(defn fibonacci [n]
2  (let [helper (fn [a b count]
3                 (if (zero? count)
4                   a
5                   (recur b (+ a b) (dec count))))]
6    (helper 0 1 n)))
7
8(println (fibonacci 5)) ; Output: 5

Here, we use a helper function with three parameters: a and b for the current and next Fibonacci numbers, and count for the remaining iterations. The recur call updates these parameters, ensuring efficient computation without stack growth.

Visualizing Tail Recursion with recur

To better understand how recur optimizes recursion, let’s visualize the flow of a tail-recursive function using a diagram.

    flowchart TD
	    A[Start: Initial Call] --> B[Check Base Case]
	    B -->|Base Case Met| C[Return Result]
	    B -->|Base Case Not Met| D[Update Parameters]
	    D --> E[Recur: Tail Call]
	    E --> B

Diagram Explanation: This flowchart illustrates the process of a tail-recursive function using recur. The function checks the base case, updates parameters, and makes a tail call using recur, looping back to the base case check without growing the stack.

Comparing recur with Java Iteration

In Java, we often use loops to avoid recursion when dealing with large input sizes. Let’s compare a loop-based approach in Java with a recur-based approach in Clojure.

Java Iterative Factorial

 1public class IterativeFactorial {
 2    public static int factorial(int n) {
 3        int result = 1;
 4        for (int i = 1; i <= n; i++) {
 5            result *= i;
 6        }
 7        return result;
 8    }
 9
10    public static void main(String[] args) {
11        System.out.println(factorial(5)); // Output: 120
12    }
13}

Clojure Recursive Factorial with recur

1(defn factorial [n]
2  (loop [i n acc 1]
3    (if (zero? i)
4      acc
5      (recur (dec i) (* acc i)))))
6
7(println (factorial 5)) ; Output: 120

Comparison: Both implementations achieve the same result, but the Clojure version expresses the changing values as new loop bindings rather than mutable local variables. The loop construct establishes the local recursion point that recur targets.

Best Practices for Using recur

• Ensure Tail Position: Always place recur in tail position so the compiler can reuse the frame.
• Use Accumulators: When necessary, use accumulators to carry intermediate results.
• Choose the simplest loop shape: Prefer reduce for collection aggregation, loop/recur for custom state transitions, and direct recursion only when the depth is bounded.

Try It Yourself

Experiment with the following exercises to deepen your understanding of recur:

1. Modify the Fibonacci Function: Change the initial values of a and b in the Fibonacci function to see how it affects the sequence.
2. Implement a Sum Function: Write a tail-recursive function using recur to calculate the sum of a list of numbers.
3. Refactor a Java Loop: Take a loop-based Java function and refactor it into a tail-recursive Clojure function using recur.

Further Reading

For more information on recursion and recur in Clojure, consider exploring the following resources:

• Official Clojure Documentation on Recursion
• ClojureDocs: recur

Key Takeaways

• recur reuses the current frame for valid tail-position jumps, allowing long linear recursion without stack growth.
• Tail recursion requires the recursive call to be the last operation in a function or loop.
• Clojure’s recur makes state transitions explicit by passing the next values instead of mutating loop variables.
• Practice using recur to refactor recursive functions, leveraging accumulators and tail position for optimal performance.

Now that we’ve explored how recur makes loop-shaped recursion stack-safe, let’s apply these concepts to manage recursion effectively in your applications.

Quiz: Using recur in Clojure