Implementar recursión usando pilas

Otra de las aplicaciones en las que podemos utilizar las pilas es en la implementación de la recursividad. A continuación se mostrarán algunos ejemplos.

                |
                |      1 ,                  N=0
Factorial     < 
                |      N*(n-1)!,      N&gt0
                |

        sp <--0
        mientras n <> 1 haz
                 push(pila,n)
                 n<--n-1
        mientras sp <> 0 haz
                 factorial<--factorial*pop(pila)


                |
                |      0  ,               si a < b
Q             < 
                |   Q(a-b,b)+1,   si a<=b
                |

        sp<--0
        Q<--0
        lee(a), lee(b)
        mientras a>=b haz
                push(pila,1)
                a<--a-b
        mientras sp< > 0 haz
                Q<-- Q + pop(pila)

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz

Publicado en Estructura de datos

Suscríbete:

who's online