Hay muchos problemas para los cuales la recursión resulta natural y para los cuales la iteración resulta extremadamente difícil. Esto sucede usualmente cuando se tienen en cuenta objetos con una estructura compleja de listas anidadas. Por ejemplo, consideremos esta expresión matemática en formato LISP:

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

Math-formula contiene listas dentro de listas dentro de listas.

Supongamos que quisiéramos saber cuántos números están sepultados en las profundidades de esta fórmula. He aquí una función recursiva que lo averiguará:

(defun num-nums (mf)
  (cond 
    ((null mf) 0)                  ;; la lista vacía no contiene ninguno
    ((numberp (car mf))            ;; si el primer término es un número
      (1+ (num-nums (cdr mf))))    ;; sumar al número en el resto
    ((atom (car mf))               ;; si es cualquier otro átomo
      (num-nums (cdr mf)))         ;; ignorarlo, contar el resto
    (t (+ (num-nums (car mf))      ;; o se trata de una lista a contar
          (num-nums (cdr mf))))))  ;; y sumar al numero en el resto

Pruebe esta función y examine su operación usando TRACE. Observe que la profundidad de recursión fluctúa a medida que las sublistas son procesadas.

>(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

Sería difícil definir num-nums de forma iterativa. No es imposible, pero exige el saber utilizar una pila para simular la recursión.

Muchas tareas de inteligencia artificial implican el buscar a través de estructuras anidadas. Por ejemplo, las representaciones en árbol de los movimientos en un juego se representan mejor como listas anidadas. Examinar este árbol implica un rastreo recursivo a través del mismo. Para este tipo de aplicación las funciones recursivas resultan una herramienta esencial.

¿Cuándo debemos utilizar la iteración y cuándo la recursión? Hay por lo menos estos tres factores a considerar:

(1)

La funciones iterativas son usualmente más rápidas que sus contrapartes recursivas. Si la velocidad es importante, normalmente usaríamos la iteración.

(2)

Si la memoria de pila es un limitante, se preferirá la iteración sobre la recursión.

(3)

Algunos procedimientos se programan de manera recursiva de forma muy natural, y resultan prácticamente inabordables iterativamente. Aquí la elección es clara.