PDF de programación - Tema VII. Recursividad

Tema VII. Recursividad.

Recursividad. Concepto. Recursividad directa e

indirecta. Recursividad versus iteración.

Recursividad infinita. Ejemplos de problemas de

recursividad. Ventajas y desventajas.

Mgter. Oscar Adolfo Vallejos
FaCENA - UNNE

Recursividad

Premisas

• Las definiciones recursivas suelen responder a funciones que

se definen en base a un caso menor de sí mismas. Pero la
recursividad en programación tiene otras implicaciones.

• Substancial diferencia entre una función matemática y un

función programada.

• La recursividad en programación, aunque está permitida en

prácticamente todos los lenguajes modernos, no es una
herramienta demasiado útil en un entorno productivo.

• ¿Cuándo debo utilizar entonces recursividad?

Recursividad

Introducción

• El concepto de recursión aparece en varias situaciones de la vida

cotidiana, aunque en muchas no sabemos que estamos en
presencia de este concepto, por ejemplo, sacar fotocopias de
fotocopias, tomar una fotografía a otra fotografía.

•

La recursión como herramienta de programación permite definir un
objeto (por ejemplo una estructura de datos - en términos de si
mismo. Un caso concreto de recursión ya visto en apartados
anteriores son las listas circulares, en donde una lista se llama a si
misma.

• Un ejemplo clásico en matemática es el factorial de un número,

potencia o la serie de Fibonacci.

Recursividad

Concepto

• Un programa o subprograma que se llama a si mismo se dice que es recursivo.

•

•

El concepto de recursividad está ligado, en los lenguajes de programación, al
concepto de procedimiento o función. Un procedimiento o función es recursivo
cuando durante una invocación a él puede ser invocado a su vez él mismo.

La recursividad es una de las formas de control más importantes en la
programación. Los procedimientos recursivos son la forma más natural de
representación de muchos algoritmos.

• Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de

construcción. La base no es recursiva y es el punto tanto de partida como de
terminación de la definición.

Recursividad

Concepto

Entonces:

Base: La secuenciación, iteración condicional y selección son estructuras válidas
de control que pueden ser consideradas como enunciados.

Regla recursiva: Las estructuras de control que se pueden formar combinando de
manera válida la secuenciación iteración condicional y selección también son
válidos.

Un conjunto de objetos está definido recursivamente siempre que:

(B) algunos elementos del conjunto se especifican explícitamente
(R) el resto de los elementos del conjunto se definen en términos de los lementos
ya definidos, donde

(B) se llama base
(R) se llama cláusula recursiva

Recursividad

Concepto

Observaciones:

1. El procedimiento se llama a si mismo
2. El problema se resuelve, resolviendo el mismo problema pero de tamaño

menor

3. La manera en la cual el tamaño del problema disminuye asegura que el caso
base eventualmente se alcanzará.

Aplicaciones

La recursividad es un método poderoso usado en inteligencia artificial, su poder
es que algunos conceptos complejos pueden expresarse en una forma simple.

Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de
teoremas, solución de problemas combinatorios, algunos acertijos, etc.

Recursividad como técnica de Programación

• Una Técnica de programación que tiene su origen en

ciertos cálculos matemáticos.

• Consiste en describir los cálculos (o acciones) de una

manera autoalusiva (resolver problemas
describiéndoles en términos de ejemplares mas
sencillos de si mismos.

• Esta técnica puede entenderse como un caso

particular de programación estructurada.

Un ejemplo de referencia

Consideremos el cálculo del factorial de un entero positivo n que se define de

la siguiente forma:

Como, a su vez,

tenemos que n! se puede definir en términos de (n - 1)!, para
n > 0, así:

siendo por definición 0! = 1, lo que permite terminar correctamente los cálculos.
Por ejemplo, al calcular el factorial de 3:

Por lo tanto, si n es distinto de cero tendremos
que calcular el factorial de n - 1, y si es cero el
factorial es directamente 1:

La definición anterior podemos escribirla en Diagrama de Flujo,

Pseudo y su correspondiente codificación en Pascal …

Al ejecutarlo sobre el argumento 4, se produce

la cadena de llamadas sucesivas a
Fac(4), Fac(3), Fac (2), Fac(1) y a Fac(0), así:

En resumen

Los subprogramas recursivos se caracterizan por la posibilidad de

invocarse así mismos.

Debe existir al menos un valor del parámetro sobre el que se hace la

recursión, llamado caso base, que no provoca un nuevo cálculo
recursivo, con lo que finaliza y puede obtenerse la solución; en el
ejemplo del factorial, es el cero.

Si este valor no existe, el cálculo no termina. Los restantes se llaman

casos recurrentes, y son aquéllos para los que sí se produce un nuevo
cálculo recursivo; en el ejemplo, se trata de los valores positivos 1, 2,
3. . .

En las sucesivas llamadas recursivas los argumentos deben aproximarse a

los casos base,

Esquema de llamadas de Fac

El proceso de ejecución de un subprograma recursivo consiste en una cadena

de generación de llamadas (suspendiéndose los restantes cálculos) y
reanudación de los mismos al término de la ejecución de las llamadas

Para comprender mejor el funcionamiento de un subprograma

recursivo, recordemos el proceso de llamada a un subprograma
cualquiera:

• Se reserva el espacio en memoria necesario para almacenar los

parámetros y los demás objetos locales del subprograma.

• Se reciben los parámetros y se cede la ejecución de instrucciones al

subprograma, que comienza a ejecutarse.

• Al terminar éste, se libera el espacio reservado, los identificadores

locales dejan de tener vigencia y pasa a ejecutarse la instrucción
siguiente a la de llamada.

En el caso de un subprograma recursivo, cada llamada genera un nuevo ejemplar del

subprograma con sus correspondiente objetos locales. Podemos imaginar cada
ejemplar como una copia del subprograma en ejecución.

•

•

•

•

•

El subprograma comienza a ejecutarse normalmente y, al llegar a la llamada, se
reserva espacio para una nueva copia de sus objetos locales y parámetros. Estos
datos particulares de cada ejemplar generado se agrupan en la llamada tabla de
activación del subprograma.

El nuevo ejemplar del subprograma pasa a ejecutarse sobre su tabla de activación,
que se amontona sobre las de las llamadas recursivas anteriores formando la
llamada pila recursiva.

Este proceso termina cuando un ejemplar no genera más llamadas recursivas por
consistir sus argumentos en casos básicos.

Entonces, se libera el espacio reservado para la tabla de activación de ese ejemplar,
reanudándose las instrucciones del subprograma anterior sobre la tabla penúltima.

Este proceso de retorno finaliza con la llamada inicial.

Recursión Directa e Indirecta

Directa: El subprograma se llama directamente

a si mismo.

Recursión Directa e Indirecta

Indirecta: Un programa llama a otro subprograma y este a su vez al primero El

subprograma A llama al B y este a su vez llama al primero A, es decir que
luego de tantas llamadas el control regresa al subprograma A. Otro caso de
recursión indirecta es el caso b) de la figura, que muestra como un
subprograma llama a otro y este a un tercero y una vez ejecutado el
subprograma vuelve a donde fue llamado. En el ejemplo de la figura el
programa A llama al B y este al C; cuando finaliza la ejecución C vuelve a
donde fue llamado B y este a su vez al subprograma A – programa inicio.

En toda definición
recursiva de un
problema se debe
establecer un estado
básico. Es decir un
estado en el cual la
solución no se presente
de manera recursiva,
sino directamente.
Además la entrada
(datos) del problema
debe ir acercándose al
estado básico.

¿Cómo funciona la recursividad?

4!=4*3!

3!=3*2!

2!=2*1!

1!=1*0!=1*1

Recursividad Infinita

Recursividad Infinita

• Es muy importante que toda función recursiva

tenga un caso en el que no se llame a sí misma, o
las llamadas serían infinitas y el programa no
tendría fin.

• Por eso, siempre una función recursiva tiene una

condición inicial en la que no debe llamarse a sí
misma.

Funcionamiento Interno del Ej. Factorial

Funcionamiento Interno del Ej. Factorial

Cuando esta función es invocada, por ejemplo, para hallar el factorial

del número 3, se crean en la memoria de la computadora las
siguientes instancias:

y al finalizar comienza el retorno a la invocación anterior efectuándose las acciones que
habían quedado pendientes.:

Ejemplo 2: Serie de Fobonaci

Ejemplo 3: Torres de Hanoi
Un problema típico a resolver con recursión es el de las Torres de

Hanoi, ya que al aplicar esta herramienta el problema se simplifica
enormemente. Las Torres de Hanói es un rompecabezas o juego
matemático inventado en 1883 por el matemático francés Éduard
Lucas

Consiste en tres varillas verticales y un número indeterminado de discos que
determinarán la complejidad de la solución. No hay dos discos iguales, están
colocados de mayor a menor en la primera varilla ascendentemente, y no se
puede colocar ningún disco mayor sobre uno menor a él en ningún
momento..

Llamaremos A, B y C a cada una de las agujas sin importar el orden

siempre que se mantengan los nombres.

Consideremos inicialmente dos discos en A que queremos pasar a B

utilizando C como auxiliar. Las operaciones por realizar son
sencillas:

• Ahora supongamos que tenemos tres discos en A y queremos

pasarlos a B.

• Haciendo algunos tanteos descubrimos que hay que pasar los dos

discos superiores de A a C, mover el último disco de A a B y por
último pasar los dos discos de C a B. Ya conocemos cómo pasar dos
discos de A a B usando C como auxiliar, para pasarlos de A a C
usaremos B como varilla auxiliar y para pasarlos de C a B usaremos
A como auxiliar: