algorithm - recursivo - recursividad pdf

¿Cómo puedo calcular el número de veces que se ejecutará una función específica en la recursión?

Question

Esta pregunta es en referencia al código de soplado:

cost = [[1, 10, 75, 92],
         [-1, 0, 35, 50],
         [-1, -1, 0, 80],
         [-1, -1, -1, 0]]

def min_cost(source, destination):
   if s==d or s == d-1:
       return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
return mc

Cuando hice la ejecución en seco del mismo, vi que min_cost (1,3) se ejecutaba 2 veces. Leí en un libro donde el autor mencionó que si teníamos 10 estaciones entre ellas, min_cost (1, 3) correría 144 veces.

¿Cómo podemos averiguar estos números sin hacer realmente la ejecución en seco? Sé que mediante el uso de ecuaciones de recursión podemos calcular el tiempo que toma la función, pero ¿cómo se puede decir que una función específica se ejecutará tantas veces?

Answer 1

Creo que una variable global que se encuentra fuera de la función (un miembro de su clase si está en Java, o una var. Global en C ++ / C) y que aumenta su valor en uno cada vez que la llame, hará el truco.

Answer 2

Hay varias opciones para calcular esa cantidad cuando uno está trabajando con recursión. Lo más simple sería agregar otra variable al método recursivo que se incrementa cada vez que se recurre y en la última declaración donde se devuelve no se incrementa, sino que se devuelve la última cantidad, la cual regresará a la parte superior. solicitud.

Ejemplo en pseudo código:

function recursionfunction(x, y, recursioncount) {
    if(expressionIsFalse) {
        recursionfunction(x, y, recursioncount+1);
    } else {
        return recursioncount;
    }
}

print recursionfunction('''','''', 0);

Otra forma de trabajar es asignando una variable por referencia, un puntero o una variable global (según el lenguaje de programación) e incrementando ese contador.

¿Te ayudó esto?

Answer 3

Si bien comprendo que no desea un recorrido en seco para simplemente contar las llamadas, me gustaría hacerlo primero, solo para ver qué está pasando. Entonces, aquí va:

def min_cost(s, d):
    global count
    count += 1
    if s==d or s == d-1:
        return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
    return mc

for n in range (2, 8):
    cost = [[0 for i in range (n)] for j in range (n)]
    count = 0
    min_cost(0, n-1)
    print (str (n) + '': '' + str (count))

La salida es:

2: 1
3: 3
4: 9
5: 27
6: 81
7: 243

Entonces, vemos que el número de llamadas para ds = k es 3 a la potencia de (k-1). Saber lo que tenemos que probar a veces simplifica enormemente encontrar la prueba.

Ahora, a la prueba en sí. Será prueba por inducción . Primero, tenga en cuenta que el número de llamadas de min_cost(s, d) depende solo del valor de ds , y no de los valores individuales de s d .

La base es que, para ds=1 , recibimos una llamada. Para ds>1 , hacemos nuestra única llamada, y de ella las siguientes llamadas:

min_cost(s, s+1) and min_cost(s+1, d)
min_cost(s, s+2) and min_cost(s+2, d)
...
min_cost(s, d-1) and min_cost(d-1, d)

Entonces, para ds=k , el número de llamadas f(k) es:

f(k) = 1 +
       f(1) + f(k-1) +
       f(2) + f(k-2) +
       ... +
       f(k-1) + f(1)
     = 2 * (f(1) + f(2) + ... + f(k-1))

Si, por la hipótesis de inducción, ya hemos probado que f (v) = 3 ^v para todos v <k, entonces f (k) es:
1 + 2 * (3 ¹ + 3 ² + ... + 3 ^k-1 ), que es trivially 3 ^k , completando nuestra prueba.

Por último, tenga en cuenta que, si bien el algoritmo presentado es exponencial, el problema subyacente se puede resolver en tiempo polinomial, más simplemente en O ((ds) ^ 2) mediante la memorización de las llamadas para las cuales ya hemos realizado todo el trabajo.