Funciones recursivas

Definición recursiva de una función

Especificar formalmente la función.-

• Nombre de la función

• Nombre y tipo del conjunto inicial (dominio)

• Nombre y tipo del conjunto final (imagen)

• Precondición y postcondición.

Describir el principio de inducción utilizado.-

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.

Realizar el Análisis por casos (valores de la función).-

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.

Escribir el algoritmo en pseudocódigo

Verificar formalmente la corrección del algoritmo

El siguiente esquema describe el modelo general en el que deben encuadrarse las funciones recursivas:

{Q($\bar{x}$)}

función f(x: T1) retorna (y: T2) 
    caso
    Bt(x) -> triv(x) 
    Bnt(x) -> c(f(s(x)), x)
    fcaso 
ffunción

{R($\bar{x}, \bar{y}$)}

donde los parámetros formales $\bar{x}$ e $\bar{y}$ han de entenderse como tuplas { $x_1, x_2,...,x_n$} e { $y_1, y_2,...,y_n$} , respectivamente.

Las expresiones booleanas $B_t$ y $B_{nt}$ distinguen, respectivamente si el problema $\bar{x}$ es trivial o no. Obviamente ha de cumplirse

para todo $\bar{x}$ que satisfaga la precondición { Q($\bar{x}$)}

triv: T1 $\longrightarrow$ T2 es una función que calcula la solución de f cuando $\bar{x}$ es trivial

s: T1 $\longrightarrow$ T1 es la función sucesor y realiza la descomposición recursiva de los datos $\bar{x}$, calculando el subproblema $\bar{x'}$ de $\bar{x}$, al cual se le aplica la invocación recursiva de f

denotaremos s($\bar{x}$) como $\bar{x}'$ y f(s($\bar{x}$)) como $\bar{y}'$

c: T2 x T1 $\longrightarrow$ T2 es la función de combinación y combina el resultado devuelto por f para $\bar{x}'$ con (todos o parte de) los propios parámetros de entrada $\bar{x}$

R es la postcondición de f que establece la relación que ha de cumplirse entre los parámetros de entrada $\bar{x}$ y los resultados $\bar{y}$

Q es la precondición de f y establece los estados válidos para invocar a la función f