Hay muchos problemas para los cuales la recursiónresulta natural y para los cuales la iteración resulta extremadamentedifícil. Esto sucede usualmente cuando se tienen en cuenta objetos conuna estructura compleja de listas anidadas. Por ejemplo, consideremos estaexpresió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 delistas.

Supongamos que quisiéramos saber cuántos númerosestán sepultados en las profundidades de esta fórmula. Heaquí 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ónusando TRACE. Observe que la profundidad de recursión fluctúa amedida 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 formaiterativa. No es imposible, pero exige el saber utilizar una pila para simularla recursión.

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

¿Cuándo debemos utilizar la iteración y cuándola 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 muynatural, y resultan prácticamente inabordables iterativamente.Aquí la elección es clara.