Funciones recursivas
Last updated
Last updated
Nombre de la función
Nombre y tipo del conjunto inicial (dominio)
Nombre y tipo del conjunto final (imagen)
Precondición y postcondición.
Estudiar cómo se pueden descomponer recursivamente los datos del problema, de forma que podamos calcular la solución pedida a partir de una o más soluciones del propio problema para datos más pequeños.
Analizar los casos que se puedan presentar a la función, identificando bajo qué condiciones el problema ha de considerarse TRIVIAL y cuál ha de ser la solución a aplicar en ese caso, y bajo qué condiciones el problema ha de considerarse NO TRIVIAL y cómo ha de resolverse entonces.
Verificar formalmente la corrección del algoritmo
El siguiente esquema describe el modelo general en el que deben encuadrarse las funciones recursivas:
{Q()}
función f(x: T1) retorna (y: T2)
caso
Bt(x) -> triv(x)
Bnt(x) -> c(f(s(x)), x)
fcaso
ffunción
Q es la precondición de f y establece los estados válidos para invocar a la función f
{R()}
donde los parámetros formales e han de entenderse como tuplas { } e { } , respectivamente.
Las expresiones booleanas y distinguen, respectivamente si el problema es trivial o no. Obviamente ha de cumplirse
para todo que satisfaga la precondición { Q()}
triv: T1 T2 es una función que calcula la solución de f cuando es trivial
s: T1 T1 es la función sucesor y realiza la descomposición recursiva de los datos , calculando el subproblema de , al cual se le aplica la invocación recursiva de f
denotaremos s() como y f(s()) como
c: T2 x T1 T2 es la función de combinación y combina el resultado devuelto por f para con (todos o parte de) los propios parámetros de entrada
R es la postcondición de f que establece la relación que ha de cumplirse entre los parámetros de entrada y los resultados