¿Cómo puedo determinar el tiempo de ejecución de una función recursiva doble?

Sigues cambiando tu función. Pero sigue eligiendo los que se ejecutarán para siempre sin conversión ...

La recursión se complica, rápido. El primer paso para analizar una función doblemente recursiva propuesta es intentar rastrearla en algunos valores de muestra, para ver qué hace. Si su cálculo llega a un bucle infinito, la función no está bien definida. Si su cálculo se introduce en una espiral que sigue obteniendo números más grandes (lo que ocurre muy fácilmente), probablemente no esté bien definido.

Si rastrearlo da una respuesta, entonces intentas encontrar algún patrón o relación de recurrencia entre las respuestas. Una vez que tenga eso, puede intentar averiguar su tiempo de ejecución. Descubrirlo puede ser muy, muy complicado, pero tenemos resultados como el Teorema maestro que nos permiten descubrir la respuesta en muchos casos.

Tenga en cuenta que, incluso con una sola recursión, es fácil encontrar funciones cuyo tiempo de ejecución no sepamos calcular. Por ejemplo, considere lo siguiente:

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

Es actualmente desconocido si esta función siempre está bien definida, por no hablar de cuál es su tiempo de ejecución.

El tiempo de ejecución de ese par de funciones en particular es infinito porque ninguno de los dos regresa sin llamar al otro. El valor de retorno de a depende siempre del valor de retorno de una llamada a b que siempre llama a ... y eso se conoce como < em> recursión infinita .

El método obvio es ejecutar la función y medir cuánto tarda. Sin embargo, esto solo le dice cuánto tiempo le toma a una entrada particular. Y si no sabe de antemano que la función termina, difícil: no hay una forma mecánica de averiguar si la función termina, esa es la detener problema , y es indecidible.

Encontrar el tiempo de ejecución de una función es igualmente indecidible, por Teorema de Rice . De hecho, el teorema de Rice muestra que incluso decidir si una función se ejecuta en O(f(n)) tiempo es indecidible.

Entonces, lo mejor que puedes hacer en general es usar tu inteligencia humana (que, por lo que sabemos, no está limitada por los límites de las máquinas de Turing) e intentar reconocer un patrón o inventar uno. Una forma típica de analizar el tiempo de ejecución de una función es convertir la definición recursiva de la función en una ecuación recursiva en su tiempo de ejecución (o un conjunto de ecuaciones para funciones recursivas mutuas):

T_a(x) = if x ≤ 0 then 1 else T_b(x-1) + T_a(x-1)
T_b(x) = if x ≤ -5 then 1 else T_b(T_a(x-1))

¿Qué sigue? Ahora tiene un problema de matemáticas: necesita resolver estas ecuaciones funcionales. Un enfoque que a menudo funciona es convertir estas ecuaciones en funciones enteras en ecuaciones en funciones analíticas y usar el cálculo para resolverlas, interpretando las funciones T_a y T_b como generar funciones .

Sobre la generación de funciones y otros temas de matemáticas discretos, recomiendo el libro Matemáticas concretas , por Ronald Graham, Donald Knuth y Oren Patashnik.

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.

Lo primero que debe hacer es mostrar que las funciones que ha definido terminan y para qué valores exactamente. En el ejemplo que has definido

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

b solo termina para y <= -5 porque si conecta cualquier otro valor, tendrá un término del formulario b(a(y-1)) . Si se expande un poco más, verá que un término de la forma b(a(y-1)) finalmente conduce al término b(1010) , que conduce a un término b(a(1009)) , que nuevamente conduce al término b(1010) . Esto significa que no puede insertar ningún valor en a que no satisfaga a x <= -4 porque si lo hace termina con un bucle infinito donde el valor que se debe calcular depende del valor que se va a calcular. Básicamente, este ejemplo tiene un tiempo de ejecución constante.

Entonces, la respuesta simple es que no existe un método general para determinar el tiempo de ejecución de las funciones recursivas porque no existe un procedimiento general que determine si una función definida recursivamente termina.

Runtime como en Big-O?

Eso es fácil: O (N) - asumiendo que hay una condición de terminación.

La recursión es solo un bucle, y un bucle simple es O (N) sin importar cuántas cosas haga en ese bucle (y llamar a otro método es solo otro paso en el bucle).

Lo interesante sería si tiene un bucle dentro de uno o más de los métodos recursivos. En ese caso, terminaría con algún tipo de rendimiento exponencial (multiplicando por O (N) en cada paso a través del método).