Contents Next: Tail Recursion Up: Recursion and Iteration Previous: Iteration Using Dolist

When To Use Recursion/When To Use Iteration

So far, the two examples of operations presented are just as easy to program recursively as iteratively. However, there are many problems for which recursion is natural and iteration is extremely difficult. This typically arises when considering objects with a complex nested list structure. For example, consider this Lisp-format mathematical expression:

> (setf math-formula '(+ 3 (* (- 5 pi) 4 (/ 3 7)) (* 15 2)))
(+ 3 (* (- 5 PI) 4 (/ 3 7)) (* 15 2))

Math-formula contains lists within lists within lists.

Suppose we would like to know how many numbers are buried in the depths of this formula. Here is a recursive function that will find out:

(defun num-nums (mf)
  (cond 
    ((null mf) 0)                  ;; empty list has none
    ((numberp (first mf))          ;; if first is number
     (1+ (num-nums (rest mf))))    ;; add to number in rest
    ((atom (first mf))             ;; if it's any other atom
     (num-nums (rest mf)))         ;; ignore it, count rest
    (t (+ (num-nums (first mf))    ;; else it's a list to count
          (num-nums (rest mf)))))) ;; and add to num in rest

Try this function out and watch it using trace. Notice that the depth of recursion fluctuates as sub-lists are processed.

> (num-nums math-formula)
  1>  (NUM-NUMS (+ 3 (* (- 5 PI) 4 (/ 3 7)) (* 15 2)))
    2>  (NUM-NUMS (3 (* (- 5 PI) 4 (/ 3 7)) (* 15 2)))
      3>  (NUM-NUMS ((* (- 5 PI) 4 (/ 3 7)) (* 15 2)))
        4>  (NUM-NUMS (* (- 5 PI) 4 (/ 3 7)))
          5>  (NUM-NUMS ((- 5 PI) 4 (/ 3 7)))
            6>  (NUM-NUMS (- 5 PI))
              7>  (NUM-NUMS (5 PI))
                8>  (NUM-NUMS (PI))
                  9>  (NUM-NUMS NIL)
                  <9 (NUM-NUMS 0)
                <8 (NUM-NUMS 0)
              <7 (NUM-NUMS 1)
            <6 (NUM-NUMS 1)
            6>  (NUM-NUMS (4 (/ 3 7)))
              7>  (NUM-NUMS ((/ 3 7)))
                8>  (NUM-NUMS (/ 3 7))
                  9>  (NUM-NUMS (3 7))
                    10>  (NUM-NUMS (7))
                    11>  (NUM-NUMS NIL)
                    <11 (NUM-NUMS 0)
                    <10 (NUM-NUMS 1)
                  <9 (NUM-NUMS 2)
                <8 (NUM-NUMS 2)
                8>  (NUM-NUMS NIL)
                <8 (NUM-NUMS 0)
              <7 (NUM-NUMS 2)
            <6 (NUM-NUMS 3)
          <5 (NUM-NUMS 4)
        <4 (NUM-NUMS 4)
        4>  (NUM-NUMS ((* 15 2)))
          5>  (NUM-NUMS (* 15 2))
            6>  (NUM-NUMS (15 2))
              7>  (NUM-NUMS (2))
                8>  (NUM-NUMS NIL)
                <8 (NUM-NUMS 0)
              <7 (NUM-NUMS 1)
            <6 (NUM-NUMS 2)
          <5 (NUM-NUMS 2)
          5>  (NUM-NUMS NIL)
          <5 (NUM-NUMS 0)
        <4 (NUM-NUMS 2)
      <3 (NUM-NUMS 6)
    <2 (NUM-NUMS 7)
  <1 (NUM-NUMS 7)
7

It would be hard to define num-nums iteratively. (It is not impossible, but requires you know how to use a stack to mimic the recursion.)

Many artificial intelligence tasks involve searching through nested structures. For example, tree representations of the moves in a game are best represented as a nested list. Searching the tree involves recursively tracking through the tree. For this kind of application, recursive function definitions are an essential tool.

When should you use iteration, and when use recursion? There are (at least) these three factors to consider:

(1): Iterative functions are typically faster than their recursive counterparts. So, if speed is an issue, you would normally use iteration.
(2): If the stack limit is too constraining then you will prefer iteration over recursion.
(3): Some procedures are very naturally programmed recursively, and all but unmanageable iteratively. Here, then, the choice is clear.