Recursividad en Informática: Tipos, Técnicas y Ejemplos

Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones

Escrito el 9 de Noviembre de 2024 en español con un tamaño de 26,8 KB

Diferencia entre Módulo Recursivo Directo o Indirecto

Módulo Recursivo Directo

Un módulo M que realiza una llamada a sí mismo se considera recursivo directo.

Módulo Recursivo Indirecto

Un módulo M que llama a otro módulo F, el cual a su vez llama a M, se considera recursivo indirecto.

Técnica General de Eliminación Usando Pilas

Definir una pila.
Sustituir cada variable local.
Envolver el resto del código en un bucle.
Por cada llamada recursiva:
- Disponer de los valores de las variables.
- Reiniciar el bucle.
- Recuperar la cima de la pila y usar el valor de retorno.
Por cada vuelta atrás:
- Preparar el valor de retorno que corresponda.
- Saltar hasta el punto del bucle según la dirección de retorno.

Mergesort: Divide y Vencerás

Esta técnica se aplica a la resolución de problemas. Trata de dividir el problema en otros más pequeños hasta que sea posible resolverlos. Es ideal para aprovechar el paralelismo de las máquinas actuales.

Si el tamaño del problema es menor de un umbral dado: aplicar un algoritmo sencillo para resolverlo o encontrar la solución directa.
Si no, dividir en subproblemas y encontrar la solución a cada uno de ellos.

Tipos de Recursividad

Recursividad Directa

Un ejemplo de recursividad directa es la función factorial, donde la función se llama a sí misma con un valor decrementado hasta llegar al caso base (0!).

Recursividad Indirecta

Un ejemplo de recursividad indirecta sería dos funciones que se llaman mutuamente.

Recursividad No Lineal

En la recursividad no lineal, a cada ciclo se producen dos o más llamadas recursivas. Un ejemplo es la función de Fibonacci.

Recursividad Infinita

La recursividad infinita ocurre cuando no existe una condición de parada que ponga fin a la recursión, lo que provoca un bucle infinito.

Estudio de la Eficiencia de un Algoritmo

Estudio Empírico

Consiste en programar los algoritmos y ejecutarlos varias veces con distintos datos de entrada.

Estudio Teórico

Consiste en determinar matemáticamente la calidad de recursos requeridos por la implementación en función del tamaño de la entrada.

Problemas del Estudio Empírico

Dependencia de los resultados obtenidos del tipo de ordenador.
Dependencia del lenguaje de programación usado.
Dependencia del traductor.
Dependencia de la pericia del programador.

Ventajas del Estudio Teórico

Independencia de la plataforma.
Es genérico.
Depende solo de las instrucciones.
No es necesario ejecutar el algoritmo para conocer su eficiencia.
Ofrece como salida una expresión matemática.

Método de Expansión

Se desarrolla la función de tiempo hasta obtener una sucesión que pueda ser evaluada.

Método de Ecuación Característica

Consiste en obtener, a partir de la recurrencia, una ecuación y hallar sus raíces.

Pasos del Método de Expansión

Obtener los primeros términos de la recurrencia dando valores a n.
Analizar los términos en la búsqueda de un patrón regular.
Comparar una expresión generalizada adecuada.
Demostrar la validez de la expresión.

Preguntas Básicas para la Búsqueda de Funciones Recursivas

Ejemplo: Función para calcular el factorial de un número.

¿Qué parámetro nos lleva hasta el caso base?
Respuesta: n
¿Cuál es el valor de dicho parámetro en el caso base?
Respuesta: n <= 1
¿Cuál es el tiempo del algoritmo para el caso base?
Respuesta: Constante.
¿Cuántas llamadas recursivas se hacen en el cuerpo para el caso general?
Respuesta: 1.
¿Cómo cambia un parámetro que se lleva al caso base?
Respuesta: Se reduce 1 unidad.
¿Cuál es el tiempo del resto del algoritmo para el caso general?
Respuesta: Constante.

Pasos para Diseñar un Tipo de Dato Abstracto (TDA)

Diseño Lógico Abstracto

Definir el formato del TDA.
Definir las operaciones que contempla.

Especificación

Declarar la estructura de datos que reflejará el formato definido anteriormente.
Declarar la signatura de cada una de las operaciones (sintaxis de invocación).

Implementación

Detalles de representación de la estructura de datos.
Codificación de los algoritmos para cada una de las operaciones.

Principio de Ocultación de Información

La ocultación de decisiones de diseño en un programa susceptible de cambios con la idea de proteger a otras partes del código si estos se producen. Proteger una decisión de diseño supone proporcionar una interfaz estable que proteja el resto del programa de la implementación (susceptible de cambios). Un TDA se basa en el principio de ocultación de información encapsulando los detalles y ofreciendo al exterior únicamente una interfaz de acceso.

Método para Resolver un Problema

Formulación y especificación del problema: (qué problema, finalidad, quién tiene conocimiento, especificación formal del problema).
Diseño de una solución.
Implementación de la solución: (selección de herramientas, traducción a código, revisión y refinamiento).
Prueba y documentación de la aplicación: (hace lo necesario, lo que necesita el usuario, documentación de uso).
Documentación: (implícita o explícita).
Valoración de la solución: (estructuración, legibilidad, medidas de eficiencia).

Fundamentos del Diseño de Software

El software se descompone en componentes llamados módulos, para que el software sea más manejable. Se utiliza la técnica divide y vencerás.

1. Abstracción

Abstracción Procedimental

Reducción de una secuencia de acciones a una denominación simple.

Abstracción de Datos

Diseño de tipos de datos complejos a partir de los ya existentes.

Abstracción de Control

Flujo completo abstraído.

2. Arquitectura del Sistema

Aplicación de patrones arquitectónicos y división del sistema en capas.

3. Independencia Funcional

Máxima Cohesión

Cada módulo se encarga de una única tarea y lo hace de manera global.

Mínimo Acoplamiento

Los cambios en un módulo no provocan modificaciones en otros módulos.

4. Arquitectura del Software

Organización jerárquica, interacción y estructuras.

5. Jerarquía de Control

Visibilidad y conectividad.

6. División Estructural

Presentación, aplicación y datos.

7. Estructura de Datos

Listas, pilas, colas.

8. Procedimientos del Software

9. Ocultamiento de Información

Permite independencia entre módulos.

10. Refinamiento

11. Modularidad

Ejemplo de Recursividad

int contarOcurrencias(int[] vector, int objetivo, int primero) {
  if (primero > vector.length - 1) {
    return 0;
  } else {
    if (vector[primero] == objetivo) {
      return (1 + contarOcurrencias(vector, objetivo, primero + 1));
    } else {
      return (contarOcurrencias(vector, objetivo, primero + 1));
    }
  }
}

Divisible entre 3

int recorreVector(int vector[], int primero) {
  int a = 3;
  if (primero > vector.length - 1) {
    return 0;
  }
  if (vector[primero] % a == 0) {
    return (1 + recorreVector(vector, a, primero + 1));
  } else {
    return (recorreVector(vector, a, primero + 1));
  }
}

Características de los Problemas Recursivos

Los problemas que pueden ser resueltos de forma recursiva cumplen con las siguientes características:

Problemas que pueden ser redefinidos en términos de uno o más problemas, idénticos en naturaleza al problema original, pero menores en tamaño.
Uno o más subproblemas tienen una solución directa o no recursiva.
Aplicando la redefinición del problema en términos de problemas más pequeños, dicho problema se reduce sucesivamente a los subproblemas cuyas soluciones se conocen directamente.
La solución a los problemas más simples se utiliza para construir la solución al problema inicial.

Preguntas Básicas para la Búsqueda de Soluciones Recursivas

¿Cómo se puede definir el problema en términos de uno o más problemas más pequeños del mismo tipo que el original?
¿Qué instancias del problema harán de caso base?
Conforme el problema se reduce de tamaño, ¿se alcanzará el caso base?
¿Cómo se usa la solución del caso base para construir una solución correcta al problema original?

Reglas Generales para el Paso de Parámetros

Pasar por copia los parámetros para saber si se ha alcanzado el caso base.
Si el programa guarda valores en alguna variable o vector, esta se pasa por referencia.
Los vectores y estructuras grandes se pasan por referencia.

Ventajas, Desventajas y Problemas de la Recursividad

Ventajas

Permite encontrar soluciones sencillas a problemas aparentemente muy complejos.
La ineficiencia de una implementación recursiva puede mejorarse a través de programación dinámica.
Siempre es posible transformar una solución recursiva en iterativa.

Desventajas

Fuente de problemas si no se define adecuadamente el caso base o no converge hacia el mismo.
La solución no ha de ser eficiente, por el número de llamadas y el espacio que ocupa el almacenamiento de la pila.
Es una herramienta muy potente, pero también es muy peligrosa, por lo que hay que aprender a usarla con cuidado.
Tiene sus aplicaciones y no ha de utilizarse indiscriminadamente para resolver todos los tipos de problemas.

Problemas

Ineficiencia inherente de algunas implementaciones recursivas.
Tiempo añadido para gestionar las invocaciones recursivas y correspondientes vueltas atrás.
Desbordamiento de la pila si la profundidad en la convergencia al caso base es muy alta.
Repetición innecesaria de pasos ya ejecutados en ciclos previos del proceso de recursión.

Backtracking

Técnica de construcción incremental de soluciones a un problema. La solución puede ser única o no. Realiza una búsqueda sistemática por todas las posibles configuraciones del espacio de búsqueda. Basado en el algoritmo de búsqueda en profundidad recursiva:

Cada nodo representa un estado que puede representar una solución o no.
Las aristas salientes representan acciones, decisiones que alteran el estado de la solución que está construyéndose.
Si una arista lleva a una configuración no válida se vuelve atrás hacia el nodo padre.
Si una arista lleva a una solución se guarda y comunica y el proceso puede detenerse o continuar según necesidad.

Método de Ordenación por Inserción

Es un algoritmo basado en intercambios de elementos adyacentes, por lo que su implementación es sencilla.

La ordenación se lleva a cabo directamente sobre la estructura original: espacio necesario O(1).
El número de comparaciones e intercambios en el peor de los casos es O(n²).
Es estable: no realiza intercambios innecesarios de elementos que cumplen la relación definida.
Se adapta a conjuntos de datos parcialmente ordenados.
Muy eficiente para conjuntos de datos pequeños o parcialmente ordenados.

Clasificación de los Datos Abstractos Según la Estructura de Datos que Utilicen

TDA Lineales

Vectores
Listas
Pilas
Colas
Colas de prioridad

TDA No Lineales

Matrices
Grafos
Redes

Otros TDA

Conjuntos
Números complejos

Ejemplo de Ordenación por Burbuja

Dada la siguiente lista: 47, 3, 32, 21, 56, 92. Después de dos pasadas de un algoritmo de ordenación, el array ha quedado dispuesto: 3, 32, 47, 21, 56, 92. ¿Qué algoritmo de ordenación está utilizando (selección, burbuja o inserción)? Justifica la respuesta.

Utiliza el algoritmo de ordenación por burbuja, ya que compara los términos y si el primero es menor que el segundo sus valores se intercambian. Esta comparación se va repitiendo hasta obtener la lista ordenada.

Razones que Justifican la Necesidad de la Herencia en la Programación Orientada a Objetos

Modelado de la realidad: Son frecuentes las relaciones de especialización/generalización entre las entidades del mundo real, por tanto es lógico que dispongamos de un mecanismo similar entre las clases de objetos.
Evitar redundancias: Toda la funcionalidad que aporta una clase de objetos es adoptada de manera inmediata por la clase que hereda, por tanto evitamos la repetición de código entre clases semejantes.
Facilitar la reutilización: Una clase no tiene por qué limitarse a recibir una serie de características de otra clase por herencia de forma pasiva. También disponen de cierto margen de adaptación de estas características.
Soporte al polimorfismo.

Funcionamiento del Algoritmo de Ordenación Quicksort

Los pasos que da este algoritmo para ordenar un conjunto de datos son los siguientes:

Se escoge un elemento del conjunto al que se denomina pivote, ya sea aleatoriamente o por métodos heurísticos.
Se generan dos subconjuntos, dejando a la izquierda todos los elementos menores (o iguales) que el pivote y a la derecha los mayores.
Se aplica recursivamente Quicksort sobre los dos subconjuntos hasta que estos alcanzan un tamaño mínimo.

TDA No Lineal: Árboles

Un árbol es un conjunto finito de elementos a los que se llama nodos, de los cuales uno de ellos actúa como raíz y de los que cuelgan los nodos hijos.

Terminología de Árboles

Orden: Número máximo de hijos que puede tener un nodo.
Profundidad de un nodo: Distancia en nodos hasta la raíz.
Altura de un nodo: Distancia máxima en nodos hasta una de sus hojas.
Altura del árbol: Altura del nodo raíz.
Nivel: Conjunto de nodos de igual profundidad.
Padre: Nodo de nivel superior al que se encuentra conectado un nodo dado.
Nodos hermanos: Nodos del mismo nivel.
Árbol lleno: Todos sus niveles tienen orden i nodos, con i = nivel.
Descendientes: Conjunto de nodos hijos de los hijos de un nodo dado.
Ascendientes: Nodos padre, abuelo de un nodo dado.
Árbol inorden: Todos los nodos del subárbol de la izquierda son menores que la raíz y todos los de la derecha son mayores.
Árbol preorden: La raíz es menor que todos los nodos del subárbol de la derecha.
Árbol postorden: La raíz es mayor que todos los nodos del subárbol de la derecha, siendo estos mayores que los del subárbol de la izquierda.

Implementación de Operaciones en Árboles

Se deben efectuar comprobaciones de las condiciones y generar el efecto de la operación, modificando los parámetros. Con esto se consigue mayor robustez en los programas y tratamiento más sencillo de los posibles errores.

Tipos de Árboles

Árbol general: Tiene cualquier orden.
Árbol binario: Es de orden 2, ningún nodo puede tener más de 2 nodos, son estructuras recursivas.
Árbol de búsqueda: Árbol binario inorden.
Árbol AVL: Equilibrado de altura.
Heap: Tiene un orden parcial, padre menor que los hijos pero no hay restricción entre hermanos.

Pasos en el Diseño de un TDA

Diseño Lógico Abstracto

Definir el formato del TDA.
Definir las operaciones.

Especificación

Declarar la estructura de datos.
Declarar la signatura de cada operación.

Implementación

Detalles de representación de la estructura de datos.
Codificación de los algoritmos para cada operación.

Descomposición Modular de un TDA

Facilita el diseño y la utilización. Se divide en dos módulos:

Archivo de cabecera (.h): Donde se declara el tipo de dato y sus variantes.
Archivo de implementación (.c): Se oculta la representación del tipo de dato y se implementa.

Para usar el TDA solo se incluye el archivo de cabecera con la especificación y se agrega al proyecto la implementación.

Concepto de Abstracción

Los programas son una combinación de estructuras de datos y de algoritmos.

Estructuras de Datos

Sirven para almacenar temporalmente en memoria la información que necesita el programa.

Tipos de Datos

El concepto de tipos de datos es una abstracción que determina:

El formato: Es la estructura de almacenamiento y ocupación en memoria.
El dominio: Conjunto de valores posibles.
Los operadores: Conjunto de operaciones permitidas.

Tipos de Datos Primitivos

Son las abstracciones de datos con las que ya cuenta el lenguaje de programación. A partir de estos se pueden crear tipos agregados y compuestos. Ejemplos: entero, carácter, float.

Tipos Agregados

Son colecciones de elementos pertenecientes a un tipo de dato primitivo. El lenguaje no cuenta con soporte de datos agregados.

Datos Compuestos

Son los compuestos de dos o más partes.

Relaciones entre Clases de Objetos

Asociación

Relación entre dos clases independientes que se mantienen durante un largo periodo de tiempo.

Agregación

Tipo de asociación en la que la clase de donde parte la relación representa el todo y las clases de relaciones las partes.

Composición

Tipo de agregación en la que la clase todo controla la existencia de las clases partes.

Herencia

Permite la construcción de una clase incorporando de manera implícita todas las características de una clase previa existente. Encontramos:

Adición: El descendiente puede añadir nuevos atributos y operaciones.
Redefinición: Redefine la implementación de una operación.
Anulación: Permite anular atributos que no van a ser usados por la herencia.

Dependencia

Refleja que la implementación de una clase depende de otra.

Clases Anidadas e Interiores

Se da cuando definimos una clase dentro de otra. Pueden ser estáticas o no. Si es no estática se dice clase interior y solo puede ser creada dentro de una clase continente, además tiene un acceso completo y directo a todos los atributos y operaciones del objeto que realiza su creación.

Ventajas de la Programación Orientada a Objetos (OOP)

Intuitiva.
Soluciones más seguras y con un mantenimiento más sencillo.
Escalabilidad de aplicaciones.
Reutilización del código.

Características de la OOP

Incorpora conceptos de abstracción, ocultación de información, encapsulamiento y herencia de los datos.
Incorpora mecanismos como herencia, polimorfismo y ligadura dinámica.

Protección y Herencia

Miembros públicos: Están accesibles desde descendientes y se heredan como públicos.
Miembros privados: No son accesibles desde los descendientes.
Miembros con acceso a nivel de paquete: Son accesibles desde los descendientes siempre y cuando estén en el mismo paquete que el ascendiente.
Miembros protegidos: Son accesibles únicamente desde los descendientes.

Razones que Justifican la Necesidad de la Herencia

Modelado de la realidad.
Evitar redundancias.
Facilitar la reutilización.
Soporte al polimorfismo.

Polimorfismo

Consiste en la posibilidad de que una referencia a objetos de una clase pueda conectarse con objetos descendientes de esta.

Ligadura Dinámica

Garantiza siempre la llamada a la versión correcta de cada función con independencia del polimorfismo.

Compilación en Java

Genera un ejecutable en bytecode. Para su ejecución necesita JRE, que está formado por una máquina virtual que lo compilará y ejecutará.

Ventajas de la Compilación en Java

Se compila solo una vez la aplicación y el bytecode es válido para cualquier plataforma.
Ejecutables pequeños.
Es muy robusto y detecta casi todos los errores.
Bytecode de pequeño tamaño.

Inconvenientes de la Compilación en Java

Velocidad de ejecución lenta.
La generalidad tiene falta de aprovechamiento de la potencia de la máquina y el sistema operativo.

Clases Abstractas

Son clases que representan conceptos genéricos. Se usan para la aplicación de la herencia para obtener las clases que representan los conceptos concretos.

Atributos

Describen el estado interno de cada objeto.

Ejemplos de Algoritmos Recursivos

Factorial de un Número

int factorial(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

Número de la Serie Fibonacci

int fibonacci(int n) {
  if (n == 1 || n == 2) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

División por Restas Sucesivas

int division(int a, int b) {
  if (b > a) {
    return 0;
  } else {
    return division(a - b, b) + 1;
  }
}

Invertir un Número

int invertir(int n, int t) {
  if (n == 0) {
    return t;
  } else {
    return invertir(n / 10, t * 10 + n % 10);
  }
}

int invertir(int n) {
  return invertir(n, 0);
}

int main() {
  int num;
  cout <<"Introduce un numero:";
  cin >> num;
  cout <<"Numero invertido:" << invertir(num) << endl;
  return 0;
}

Sumar los Dígitos de un Número

int sumarDigitos(int n) {
  if (n == 0) {
    return n;
  } else {
    return sumarDigitos(n / 10) + (n % 10);
  }
}

Multiplicación por el Método Ruso

int multiplicacionRusa(int A, int B) {
  if (A == 1) {
    return B;
  }
  if (A % 2 != 0) {
    return B + multiplicacionRusa(A / 2, B * 2);
  } else {
    return multiplicacionRusa(A / 2, B * 2);
  }
}

Sumar los Elementos de un Vector

int sumaVector(int v[], int n) {
  if (n == 0) {
    return v[n];
  } else {
    return sumaVector(v, n - 1) + v[n];
  }
}

Implementación de Pilas, Colas y Listas

Pila

typedef struct Pila {
  Telemento elemento;
  struct Pila *sig;
} Pila;

typedef Pila *TPila;

TPila nuevaPila();
int PilaVacia(TPila P);
Telemento Pop(TPila P); // Devuelve el elemento en el tope, lo saca y lo elimina.
void Push(TPila P, Telemento e); // Mete un nuevo elemento en la pila.
Telemento Peek(TPila P); // Devuelve el elemento en el tope, lo saca pero no lo elimina.
void LiberaPila(TPila P); // Libera la memoria asociada a la pila.

Cola

typedef struct NodoCola {
  Telemento elemento;
  struct NodoCola *sig;
} NodoCola;

typedef NodoCola *TnodoCola;

// ... (funciones similares a la pila, pero con Enqueue y Dequeue)

Lista

typedef struct NodoLista {
  Telemento elemento;
  struct NodoLista *sig;
} NodoLista;

typedef struct Lista {
  struct NodoLista *primero;
  struct NodoLista *ultimo;
} Lista;

typedef Lista *TLista;

TLista nuevaLista(); // Crea la lista.
int ListaVacia(TLista L); // Comprueba si está vacía.
void LiberaLista(TLista L); // Libera la memoria.
void Push(TLista L, Telemento e); // Agrega un nuevo elemento al inicio de la lista.
void Enqueue(TLista L, Telemento e); // Agrega un nuevo elemento al final de la lista.
void Insert(TLista L, Telemento e, int pos); // Agrega un elemento a la posición indicada.
Telemento First(TLista L); // Devuelve el elemento que está al inicio de la lista.
Telemento Last(TLista L); // Devuelve el elemento que está al final de la lista.
Telemento Get(TLista L, int pos); // Devuelve el elemento existente en la posición.
Telemento Find(TLista L, Telemento e); // Devuelve la posición del elemento buscado.
int Size(TLista L); // Devuelve el número de elementos.
Telemento Previous(TLista L); // Devuelve el elemento previo.
Telemento Next(TLista L); // Devuelve el elemento siguiente.

Árboles

typedef struct Nodo {
  Telemento dato;
  struct Nodo *izquierdo;
  struct Nodo *derecho;
} Nodo;

typedef Nodo *Tnodo;
typedef Tnodo Tarbol;

Tarbol crearArbol(Telemento x, Tnodo izq, Tnodo der);
void liberarArbol(Tarbol A);
void insertar(Tarbol *A, Telemento E);
void eliminar(Tarbol *A, Telemento e);
Telemento buscar(Tarbol A, Telemento E);
void postorden(Tarbol a);
void inorden(Tarbol a);
void preorden(Tarbol a);

Tablas de Dispersión

Se trata de encontrar una función f(x) que asigne a cada dato, ya sea este numérico o alfanumérico, una posición distinta.

Funciones de Dispersión

Dispersión Cerrada

Se opera sobre un vector de tamaño fijo.
Existe un límite en el número de datos que se pueden almacenar.
La resolución de colisiones tratará de recolocar los datos en elementos libres del vector.

Dispersión Abierta

Se opera sobre un vector de listas enlazadas.
No existe límite en el número de datos que se pueden almacenar.
La resolución de colisiones actúa sobre las listas enlazadas.

Dispersión Doble

Ayuda a mejorar la distribución de los datos en la tabla.

Eficiencia de las Tablas de Dispersión

Cálculo del factor de carga: Hay que maximizarlo.
Conteo del número de colisiones: Hay que minimizarlo.

Entradas relacionadas:

Etiquetas: