Recursividad

Apuntes teóricos – Sintaxis y Semántica del Lenguaje
Año 2013

Prof. Lic. María Gabriela Cerra

RECURSION
Veremos un nuevo mecanismo, una nueva técnica de diseño, para resolver
problemas: LA RECURSIÓN.
La recursión es una alternativa a la iteración o repetición, y aunque en
tiempo de ejecución y espacio de memoria ocupada la solución recursiva es menos
eficiente que la iterativa,existen numerosas situaciones en las que la recursividad
provee una solución más simple y natural a un problema.
La recursividad es una herramienta potente y útil que la aplicaremos:
- en la resolución de problemas que tengan naturaleza recursiva
- en reemplazo de la iteración cuando el lenguaje de programación elegido
NO posea ninguna estructura de control repetitiva
- cuando la solucióniterativa sea de gran complejidad respecto de la
solución recursiva
¿Qué es recursión? Es una técnica que realiza una tarea T, haciendo otra
tarea T ‘ de la misma naturaleza que T, pero en algún sentido más pequeña que la
original .
De esta forma, un algoritmo recursivo expresa la solución de un problema
de tamaño N, en términos de una llamada o invocación a sí mismo. Cada invocación
se planteasobre problemas de igual naturaleza que el original, pero de un tamaño
menor que N. Al ir reduciendo progresivamente la complejidad del problema a
resolver, llegará un momento en que la resolución será trivial y directa. Esta última
situación se denomina caso base. La forma en que se va reduciendo el tamaño del
problema original asegura que el caso base se alcance y por consiguiente, se llegue
ala solución esperada.

Un algoritmo recursivo (procedimiento o función) presenta las siguientes 3
características:
- se autoinvoca dentro de su propia definición, es decir se llama a sí
mismo dentro de su cuerpo (al menos una vez)
- presenta al menos un caso base o especial, donde se llevan a cabo
acciones distintas que aseguran la finalización del proceso y la obtención
de la solución
-en cada autoinvocación se resuelve un problema de igual naturaleza que
el original pero de menor tamaño. La reducción del tamaño del problema
asegura que se alcance el caso base.

Se deben hacer cuatro preguntas para construir una solución recursiva:
1.- Cómo representar el problema T en términos de un problema T ’ del
mismo tipo, pero más pequeño.

1

Apuntes teóricos – Sintaxis ySemántica del Lenguaje
Año 2013

Prof. Lic. María Gabriela Cerra

2.- Cómo reducir, en cada llamada recursiva, el tamaño del problema.
3.- Qué instancia del problema sirve como caso base.
4.- Qué manera de reducir el problema nos asegura que siempre será
alcanzado el caso base.

Para analizar esta técnica de diseño desde el punto de vista del uso de
memoria veamos el siguiente ejemplo.Cálculo del Factorial, se elige porque es fácil de entender y se ajusta
perfectamente al modelo dado.
Definición iterativa del factorial (con n entero positivo):
FACT (n) = n * (n-1) * (n-2) * ....* 1
FACT (0) = 1
y el factorial de un número negativo es indefinido.

Todos sabemos construir una solución iterativa para este problema
basándonos en esta definición. También podemos construir unsolución recursiva
del factorial:
FACT (n) = n * FACT (n - 1)
Esta definición carece de un elemento importante, el caso base.
Como en el diccionario, un caso debe definirse diferente de todos los
demás, de lo contrario la recursión nunca se detiene.
El caso base en la recursión es el Factorial (0) el que se define simplemente
como 1.
Dado que n se asume positivo, decrementando en 1 cada vezque se llama al
factorial se sabe que siempre será alcanzado el caso base.
Definición recursiva del factorial:
1
Factorial (n)

si n = 0

n * Factorial (n -1) si n > 0

Estudiaremos los mecanismos de ejecución de esta función recursiva.
Si calculamos el Factorial (3), usando esta definición:
Factorial (3) = 3 * Factorial (2)

2

Apuntes teóricos – Sintaxis y Semántica del...