PDF de programación - Capítulo 3 - Algoritmos recursivos

C a p í t u l o 3

A l g o r i t m o s r e c u r s i v o s



la metodología de

Los algoritmos recursivos se basan en

llamar
repetidamente la propia función en que están definidos, y son de gran utilidad en
multitud de campos en la informática.

Al finalizar el estudio de estas lecciones serás capaz de:


Conocer los fundamentos y características de los algoritmos recursivos.

Conocer el funcionamiento de las funciones recursivas.

Conocer las características fundamentales de las estructuras de datos

recursivas.

Conocer las ventajas y desventajas de las funciones recursivas frente a las

funciones iterativas.



Diseño de estructuras de datos y algoritmos

1





L e c c i ó n 1

A l g o r i t m o s r e c u r s i v o s


Introducción


Una técnica común de resolución de problemas es la división de un problema
en varios subproblemas de la misma categoría, pero de más fácil resolución. Esta
técnica se conoce como divide y vencerás.

Un ejemplo de algoritmos en los que se aplica esta técnica son los

algoritmos recursivos, en
llama a sí mismo
repetidamente, procurando simplificar o reducir el problema en cada llamada, hasta
llegar a un caso trivial de solución directa.


los cuales el algoritmo se

La recursividad es una técnica de programación que
busca resolver un problema sustituyéndolo por otros
problemas de la misma categoría, pero más simples.


La mayoría de los lenguajes soportan los algoritmos recursivos, permitiendo

que una función se llame a sí misma. En un algoritmo recursivo, los bucles típicos
de un algoritmo iterativo (para..hasta, mientras…) se sustituyen por llamadas al
propio algoritmo.



Se dice que un algoritmo es recursivo si dentro del
cuerpo del algoritmo y de forma directa o indirecta se
realiza una llamada a él mismo.



Al escribir un algoritmo recursivo, debe establecerse de algún modo cuando
debe dejar de llamarse a sí mismo, o de otra forma se repetiría indefinidamente.
Para ello, se establece una condición de salida llamada caso base.



Diseño de estructuras de datos y algoritmos

2

Se llama caso base o condición de salida al caso trivial
de un algoritmo recursivo, del cual conocemos su
solución.



El caso base contempla el caso en el cual la solución es lo suficientemente
sencilla como para responder directamente sin necesidad de realizar otra llamada al
algoritmo.


El ejemplo más típico de algoritmo recursivo es el de una
función para calcular el factorial de un número. El factorial de
un número es el resultado de multiplicar dicho número por todos los
precedentes, hasta llegar a 1. Por ejemplo, factorial(3) = 3 * 2 * 1.
Si observamos que el factorial de un número es equivalente al
producto de dicho número por el factorial del número precedente:

factorial(3) = 3 * factorial(2)
podemos plantear una implementación recursiva:


función factorial(n)



fin función

si n = 1

sino

fin si

devolver 1

devolver n * factorial(n – 1)


En este caso, la sentencia

si n = 1 devolver 1

es la condición de salida o caso base que evita que la función se
llame a sí misma indefinidamente.

Todo algoritmo recursivo debe incluir al menos un
caso base y garantizar que se ejecuta en algún
momento para evitar la recursividad infinita.



Diseño de estructuras de datos y algoritmos



3





La mayoría de los algoritmos que pueden ser descritos de
forma iterativa (es decir, haciendo uso de bucles while,
for…) pueden ser reescritos de forma recursiva, y
viceversa.


El concepto de recursividad pone una gran potencia al alcance del
programador y adquiere una dimensión fundamental en los llamados lenguajes de
programación funcionales, los cuales a menudo no incorporan sentencias que
permitan crear bucles, debiendo recurrir a
llamadas recursivas para
implementar repeticiones.

las



Para obtener más información respecto a los lenguajes de
programación funcionales, consulta la dirección Web

http://es.wikipedia.org/wiki/Programaci%C3%B3n_funcional



Se pueden establecer diferentes categorías de recursividad en virtud de la

característica del algoritmo analizada:


▪ Según el punto desde el cual se hace la llamada recursiva: recursividad
directa o indirecta.

▪ Según el número de llamadas recursivas efectuadas en tiempo de
ejecución: recursividad lineal o no lineal.

▪ Según el punto del algoritmo desde donde se efectúa la llamada recursiva:
recursividad final o no final.


Al hablar de funciones recursivas, nos referimos a algoritmos
recursivos implementados en un lenguaje particular. Aunque
hemos elegido el
función, pueden
emplearse otros similares como procedimiento o método.


término genérico

Diseño de estructuras de datos y algoritmos



4

función A
…
A(…)
…
fin función



función A
…
A(…)
…
fin función



Recursividad directa y recursividad indirecta


▪ Recursividad directa: Se da cuando la función efectúa una llamada a sí
misma.



▪ Recursividad indirecta: Se da cuando una función A llama a otra función
B la cual a su vez, y de forma directa o indirecta, llama nuevamente a A.

función A
…
B(…)
…
fin función



función B
…
A(…)
…
fin función


Recursividad lineal y recursividad no lineal



▪ Recursividad lineal o simple: Se da cuando la recursividad es directa y
además cada llamada a la función recursiva sólo hace una nueva llamada
recursiva.

▪ Recursividad no lineal o múltiple: La ejecución de una llamada
recursiva da lugar a más de una llamada a la función recursiva.


función A
…
si condición

A(…)
fin si
…
A(…)
…
fin función

La recursividad será no
lineal si se cumple
condición, pues en tal
caso se producen dos
llamadas recursivas.



Diseño de estructuras de datos y algoritmos

5




Recursividad final y recursividad no final


▪ Recursividad final: Se da cuando la llamada recursiva es la última
operación efectuada en el cuerpo de la función. (sin tener en cuenta la
sentencia devolver)


función A
…
devolver A(…)

fin función


existe

No
ningún
procesamiento posterior
a la llamada a A().



▪ Recursividad no final: Se da cuando la llamada recursiva no es la última
operación realizada dentro de la función (sin tener en cuenta la sentencia
devolver)



función A
…
devolver A(…) + 5

fin función


función A
…
devolver A(…) + A(…)

fin función


La llamada a la función
recursiva no es la última
operación efectuada (en
ambos casos es una
suma)



Explicaremos más a fondo la recursividad final en la Lección 4 –
Funciones recursivas finales.



La secuencia de Fibonacci, definida por la fórmula

fib(n) = n si n = 0 o si n = 1
fib(n) = fib(n – 2) + fib(n – 1) si n >= 2

es un ejemplo de recursividad múltiple y no final. Para el caso
n>=2 se producen dos llamadas recursivas, y al regresar de la
llamada recursiva el resultado no se devuelve tal cual sino que
se suma con el resultado de otra llamada recursiva.

Diseño de estructuras de datos y algoritmos



6




Diseño de funciones recursivas

Para escribir un algoritmo de forma recursiva es necesario intentar

transformar el problema en otro similar pero más simple, así como encontrar una
solución directa para los casos triviales.



Es necesario, pues:

▪ Identificar y formular el caso base o condición de salida del cual
conocemos la solución directamente.



▪ Formular el caso general que debe poder resolverse en función del caso
base y una transformación del caso general hacia uno más sencillo.

Diseño de estructuras de datos y algoritmos

7





L e c c i ó n 2

M e c a n i s m o d e r e c u r s i v i d a d


La pila de llamadas


funcionamiento de un algoritmo recursivo es
fundamental conocer como funciona la pila de llamadas de un programa en
ejecución.


Para comprender el

La pila de llamadas (call stack en inglés) es un
segmento de memoria basado en una estructura de
datos del tipo pila utilizada para almacenar información
relacionada con las llamadas a funciones dentro de un
programa.



Todo programa en ejecución tiene una pila asociada para éste propósito. En
los lenguajes de alto nivel (como C o Java) la gestión de la pila de llamadas la
realiza de forma automática el compilador, y el programador no necesita
preocuparse de su funcionamiento.


recursiva o no- se reserva espacio en la pila para la siguiente información:



Cuando en un punto concreto de un programa se llama a una función -sea



▪ La dirección de retorno de la función:

De modo que sea posible regresar al punto de ejecución
inmediatamente posterior al de la llamada a la función.

▪ Los parámetros de la llamada:

La función llamada obtiene los parámetros (también llamados
argumentos) de la pila. Por ejemplo, en una función para sumar dos
números, los argumentos serían los números a sumar.

▪ Espacio para las variables locales

El compilador reserva espacio en la pila para almacenar las variables
locales. La cantidad de espacio reservado es proporcional al número
de variables locales definidas y al tamaño requerido por cada variable
(carácter, entero, real…).



▪ El resultado devuelto por la función

Opcionalmente, ya que también es posible y usual devolver el
resultado de la llama a la función en uno de los registros de la CPU.



Dependiendo del lenguaje de programación y arquitectura de eje