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 larecursividad 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
• Elconcepto 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 yavisto 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, alconcepto 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 laregla 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
maneravá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
ConceptoObservaciones:
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 unaforma 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 problemasdescribié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...