Algoritmia
  • Algoritmia
    • Tema 2 - Diseño de Algoritmos Recursivos
      • Introducción
      • Inducción
      • Funciones recursivas
      • Tipos de recursión
      • Ejemplos y ejercicios
      • Especificación formal de algoritmos
      • Inmersión
      • Verificación formal
    • Tema 3 - Divide y Vencerás
      • Introducción
      • Ejemplos
    • Tema 4 -Programación Dinámica
      • Introducción
      • Problemas de optimización
    • Tema 5 - Algoritmos Voraces
      • Introducción
      • Esquema voraz
      • Algoritmos voraces que producen la solución óptima
      • Planificación de tareas
    • Tema 6 - Vuelta Atrás (Backtracking)
      • Introducción
      • Esquemas generales
      • Ejemplos
Powered by GitBook
On this page
  1. Algoritmia
  2. Tema 2 - Diseño de Algoritmos Recursivos

Funciones recursivas

Last updated 1 year ago

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(xˉ\bar{x}xˉ)}

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(xˉ,yˉ\bar{x}, \bar{y}xˉ,yˉ​)}

donde los parámetros formales xˉ\bar{x}xˉ e yˉ\bar{y}yˉ​ han de entenderse como tuplas { x1,x2,...,xnx_1, x_2,...,x_nx1​,x2​,...,xn​} e { y1,y2,...,yny_1, y_2,...,y_ny1​,y2​,...,yn​} , respectivamente.

Las expresiones booleanas BtB_tBt​ y BntB_{nt}Bnt​ distinguen, respectivamente si el problema xˉ\bar{x}xˉ es trivial o no. Obviamente ha de cumplirse

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

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

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

denotaremos s(xˉ\bar{x}xˉ) como xˉ′\bar{x}'xˉ′ y f(s(xˉ\bar{x}xˉ)) como yˉ′\bar{y}'yˉ​′

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

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