7.2.1 Writing Recursive Functions

Crafting Recursive Functions in Clojure

Recursive functions are a fundamental aspect of functional programming, allowing you to solve problems by breaking them down into smaller, more manageable components. In this section, we’ll explore how to write recursive functions in Clojure, emphasizing real-world examples like factorials, Fibonacci numbers, and tree structure traversal.

Understanding Recursion

Recursion is a technique where a function calls itself in order to solve a problem. In functional programming, recursion often replaces traditional loop constructs found in imperative languages like Java.

Example 1: Calculating Factorials

The factorial of a number n is the product of all positive integers less than or equal to n. Here’s how you can compute it recursively:

Java Implementation:

public class Factorial {
    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

Clojure Implementation:

(defn factorial [n]
  (if (zero? n)
    1
    (* n (factorial (dec n)))))

Both implementations follow the same recursive logic, but Clojure embraces the functional paradigm by using immutability.

Example 2: Fibonacci Numbers

The Fibonacci sequence is a classic example where each number is the sum of the two preceding ones. Here’s how it’s defined recursively:

Java Implementation:

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

Clojure Implementation:

(defn fibonacci [n]
  (cond
    (= n 0) 0
    (= n 1) 1
    :else (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

Tree Traversal

When traversing a tree structure, recursion becomes especially useful. Here’s an example encapsulated in a binary tree:

Clojure Implementation:

(defn tree-sum [tree]
  (if (nil? tree)
    0
    (+ (:value tree) 
       (tree-sum (:left tree)) 
       (tree-sum (:right tree)))))

This function calculates the sum of all nodes in a binary tree by recursively summing the values.

Practical Considerations

While recursive functions are elegant, they might not always be the most efficient due to stack space limitations. In such cases, tail recursion or higher-level functions like loop/recur can help optimize performance.

Exercises

Enhance your understanding by rewriting the above recursive functions using tail recursion, or by implementing additional recursive functions for tasks such as reversing a list.

Unlock new possibilities in functional programming as you harness the power of recursion within Clojure.