VERIFICACIÓN DE ALGORITMOS RECURSIVOS


Sería útil tener una técnica que nos ayudase a determinar si un algoritmo recursivo funcionará: un método muy intuitivo y comúnmente utilizado es el Método de las Tres preguntas.

Método de las tres preguntas
• La pregunta Caso-Base: ¿Existe una salida no recursiva o caso base del subalgoritmo?. Además, ¿el subalgoritmo
funciona correctamente para ella?.
• La pregunta Más-pequeño: ¿Cada llamada recursiva se refiere a un caso más pequeño del problema original?.
• La pregunta Caso-General: ¿es correcta la solución en aquellos casos no base?.


Principio de inducción
El principio de inducción utilizado en demostraciones matemáticas presenta exactamente la misma filosofía o estrategia, o si se quiere es un caso particular, de la recursividad en programación. Esta técnica se aplica según dos pasos:

1) Se supone que la propiedad requerida se verifica para el caso (N-1) y a partir de esta información se demuestra que también se cumple para el caso N.
2) Basta comprobar que esa propiedad se verifica para el caso de un N pequeño, N=1 por ejemplo, para que por iteración de la propiedad para N=1 se cumpla para cualquier N.


Recursividad indirecta
La recursividad directa se da cuando una función se llama a sí misma mientras que la indirecta ocurre cuando una función llama a una segunda, esta segunda a una tercera, así hasta que termina invocándose de nuevo a la primera, y realimentando la recursión. En este caso hay que tener cuidado en la implementación de los diferentes casos base de las diferentes funciones implicadas.


Volver al índice
Siguiente