Defining recursive functions

Recursion is one of the central methodologies of computer science. It allows us to elegantly solve problems that have cumbersome non-recursive solutions. Yet, recursive functions are discouraged in quite a few imperative programming languages in favor of non-recursive functions. Clojure does no such thing and completely embraces recursion along with all its pros and cons. In this section, we will explore how to define recursive functions.

Note

The following examples can be found in src/m_clj/c1/recur.clj of the book's source code.

In general, a function can be made recursive by simply calling it again from within the body of the function. We can define a simple function to return the first n numbers of the Fibonacci sequence as shown in Example 1.1:

(defn fibo
  ([n]
   (fibo [0N 1N] n))
  ([xs n]
   (if (<= n (count xs))
     xs
     (let [x' (+ (last xs)
                 (nth xs (- (count xs) 2)))
           xs' (conj xs x')]
       (fibo xs' n)))))

Example 1.1: A simple recursive function

Note

The Fibonacci sequence is a series of numbers that can be defined as follows:

The first element F₀ is 0 and the second element F₁ is 1.

The rest of the numbers are the sum of the previous two numbers, that is the nth Fibonacci number F_n = F_n-1 + F_n-2.

In the previously defined fibo function, the last two elements of the list are determined using the nth and last functions, and the sum of these two elements is appended to the list using the conj function. This is done in a recursive manner, and the function terminates when the length of the list, determined by the count function becomes equal to the supplied value n. Also, the values 0N and 1N, which represent BigInteger types, are used instead of the values 0 and 1.This is done because using long or integer values for such a computation could result in an arithmetic overflow error. We can try out this function in the REPL shown as follows:

user> (fibo 10)
[0N 1N 1N 2N 3N 5N 8N 13N 21N 34N]
user> (last (fibo 100))
218922995834555169026N

The fibo function returns a vector of the first n Fibonacci numbers as expected. However, for larger values of n, this function will cause a stack overflow:

user> (last (fibo 10000))
StackOverflowError   clojure.lang.Numbers.lt (Numbers.java:219)

The reason for this error is that there were too many nested function calls. A call to any function requires an additional call stack. With recursion, we reach a point where all of the available stack space in a program is consumed and no more function calls can be performed. A tail call can overcome this limitation by using the existing call stack for a recursive call, which removes the need for allocating a new call stack. This is only possible when the return value of a function is the return value of a recursive call made by the function, in which case an additional call stack is not required to store the state of the function that performs the recursive call. This technique is termed as tail call elimination. In effect, a tail call optimized function consumes a constant amount of stack space.

In fact, the fibo function does indeed make a tail call, as the last expression in the body of the function is a recursive call. Still, it consumes stack space for each recursive call. This is due to the fact that the underlying virtual machine, the JVM, does not perform tail call elimination. In Clojure, tail call elimination has to be done explicitly using a recur form to perform a recursive call. The fibo function we defined earlier can be refined to be tail recursive by using a recur form, as shown in Example 1.2:

(defn fibo-recur
  ([n]
   (fibo-recur [0N 1N] n))
  ([xs n]
   (if (<= n (count xs))
     xs
     (let [x' (+ (last xs)
                 (nth xs (- (count xs) 2)))
           xs' (conj xs x')]
       (recur xs' n)))))

Note

Downloading the example code

You can download the example code files from your account at http://www.packtpub.com for all the Packt Publishing books you have purchased. If you purchased this book elsewhere, you can visit http://www.packtpub.com/support and register to have the files e-mailed to you.

Effectively, the fibo-recur function can perform an infinite number of nested recursive calls. We can observe that this function does not blow up the stack for large values of n, shown as follows:

user> (fibo-recur 10)
[0N 1N 1N 2N 3N 5N 8N 13N 21N 34N]
user> (last (fibo-recur 10000))
207936...230626N

We should note that a call to fibo-recur can take quite a while to terminate for large values of n. We can measure the time taken for a call to fibo-recur to complete and return a value, using the time macro, as follows:

user> (time (last (fibo-recur 10000)))
"Elapsed time: 1320.050942 msecs"
207936...230626N

The fibo-recur function can also be expressed using the loop and recur forms. This eliminates the need for using a second function arity to pass the [0N 1N] value around, as shown in the fibo-loop function defined in Example 1.3:

(defn fibo-loop [n]
  (loop [xs [0N 1N]
         n n]
    (if (<= n (count xs))
      xs
      (let [x' (+ (last xs)
                  (nth xs (- (count xs) 2)))
            xs' (conj xs x')]
        (recur xs' n)))))

Example 1.3: A recursive function defined using loop and recur

Note that the loop macro requires a vector of bindings (pairs of names and values) to be passed as its first argument. The second argument to the loop form must be an expression that uses the recur form. This nested recur form calls the surrounding expression recursively by passing in the new values for the declared bindings in the loop form. The fibo-loop function returns a value that is equal to that returned by the fibo-recur function, from Example 1.2, shown as follows:

user> (fibo-loop 10)
[0N 1N 1N 2N 3N 5N 8N 13N 21N 34N]
user> (last (fibo-loop 10000))
207936...230626N

Another way to handle recursion is by using the trampoline function. The trampoline function takes a function as its first argument, followed by the values of the parameters to be passed to the supplied function. A trampoline form expects the supplied function to return another function, and in such a case, the returned function will be invoked. Thus, a trampoline form manages recursion by obtaining a return value, and invoking the returned value again if it's a function. Thus, the trampoline function avoids using any stack space. Each time the supplied function is invoked, it returns and the result gets stored in the process heap. For example, consider the function in Example 1.4 that calculates the first n numbers of the Fibonacci sequence using a trampoline:

(defn fibo-trampoline [n]
  (letfn [(fibo-fn [xs n]
            (if (<= n (count xs))
              xs
              (let [x' (+ (last xs)
                          (nth xs (- (count xs) 2)))
                    xs' (conj xs x')]
                #(fibo-fn xs' n))))]
    (trampoline fibo-fn [0N 1N] n)))

Example 1.4: A recursive function defined using trampoline

In the fib-trampoline function, the internal fibo-fn function returns either a sequence, denoted by xs, or a closure that takes no arguments, represented by #(fibo-fn xs' n). This function is equivalent to the fibo-recur function we defined earlier, even in terms of performance, shown as follows:

user> (fibo-trampoline 10)
[0N 1N 1N 2N 3N 5N 8N 13N 21N 34N]
user> (time (last (fibo-trampoline 10000)))
"Elapsed time: 1346.629108 msecs"
207936...230626N

Mutual recursion can also be handled effectively using a trampoline. In mutual recursion, two functions call each other in a recursive manner. For example, consider the function that utilizes two mutually recursive functions in Example 1.5:

(defn sqrt-div2-recur [n]
  (letfn [(sqrt [n]
            (if (< n 1)
              n
              (div2 (Math/sqrt n))))
          (div2 [n]
            (if (< n 1)
              n
              (sqrt (/ n 2))))]
    (sqrt n)))

Example 1.5: A simple function that uses mutual recursion

The sqrt-div2-recur function from Example 1.5 defines two mutually recursive functions internally, namely sqrt and div2, that repeatedly square root and halve a given value n until the calculated value is less than 1. The sqrt-div2-recur function declares these two functions using a letfn form and invokes the sqrt function. We can convert this to use a trampoline form as shown in Example 1.6:

(defn sqrt-div2-trampoline [n]
  (letfn [(sqrt [n]
            (if (< n 1)
              n
              #(div2 (Math/sqrt n))))
          (div2 [n]
            (if (< n 1)
              n
              #(sqrt (/ n 2))))]
    (trampoline sqrt n)))

Example 1.6: A function that uses mutual recursion using trampoline

In the previous sqrt-div2-trampoline function shown, the functions sqrt and div2 return closures instead of calling a function directly. The trampoline form in the body of the function calls the sqrt function while supplying the value n. Both the sqrt-div2-recur and sqrt-div2-trampoline functions take about the same time to return a value for the given value of n. Hence, using a trampoline form does not have any additional performance overhead, shown as follows:

user> (time (sqrt-div2-recur 10000000000N))
"Elapsed time: 0.327439 msecs"
0.5361105866719398
user> (time (sqrt-div2-trampoline 10000000000N))
"Elapsed time: 0.326081 msecs"
0.5361105866719398

As the preceding examples demonstrate, there are various ways to define recursive functions in Clojure. Recursive functions can be optimized using tail call elimination, by using recur, and mutual recursion, which is done using the trampoline function.