Como han señalado otros, el análisis de la recursión puede ser muy difícil muy rápido. Aquí hay otro ejemplo de tal cosa: enlace enlace
es difícil calcular una respuesta y un tiempo de ejecución para estas. Esto se debe a que estas funciones recursivas recíprocas tienen una "forma difícil".
De todos modos, veamos este sencillo ejemplo:
enlace
(declare funa funb)
(defn funa [n]
(if (= n 0)
0
(funb (dec n))))
(defn funb [n]
(if (= n 0)
0
(funa (dec n))))
Comencemos por tratar de calcular funa(m), m > 0
:
funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.
El tiempo de ejecución es:
R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way
Ahora vamos a elegir otro ejemplo, un poco más complicado:
Inspirado por enlace , que es una buena lectura en sí misma, veamos: "" Los números de Fibonacci pueden ser interpretado mediante recursión mutua: F (0) = 1 y G (0) = 1, con F (n + 1) = F (n) + G (n) y G (n + 1) = F (n). " ""
Entonces, ¿cuál es el tiempo de ejecución de F? Iremos por el otro lado.
Bueno, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Ahora R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
No es difícil ver que R (F (m)) = F (m) - por ejemplo. el número de llamadas a funciones necesarias para calcular un número de Fibonacci en el índice i es igual al valor de un número de Fibonacci en el índice i. Esto suponía que sumar dos números es mucho más rápido que una llamada de función. Si este no fuera el caso, entonces sería cierto: R (F (1)) = R (F (0)) + 1 + R (G (0)), y el análisis de esto hubiera sido más complicado, posiblemente sin una solución de forma cerrada fácil.
La forma cerrada de la secuencia de Fibonacci no es necesariamente fácil de reinventar, por no mencionar algunos ejemplos más complicados.