Universidad Andina Del Cusco

UNIVERSIDAD ANDINA DEL CUSCO
“Año del Bicentenario del Perú: 200 años de

Independencia”
recursividad en programación
ASIGNATURA: Algoritmo y Lenguaje de programación estructurada
DOCENTES: Ing. LUIS ENRIQUE DEL CARPIO CUENTAS
ALUMNO: Yarahuaman Ybarra, Martin Donato 020200719f

Recursividad en programación
La recursividad es una técnica de programación que se utiliza para realizar una llamada a una
función desde ella misma, de allí su nombre. El ejemplo más utilizado por su fácil
comprensión es el cálculo de números factoriales. Un algoritmo recursivo es un algoritmo
que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada
a sí mismo se conoce como llamada recursiva o recurrente. Generalmente, si la primera
llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva
ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el
original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente
la complejidad del problema a resolver, llegará un momento en que su resolución sea más o
menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no
recursiva). En esa situación diremos que estamos ante un caso base de la recursividad
Programación Recursiva:
Es mucho más difícil desarrollar una solución recursiva en un lenguaje determinado para
resolver un problema específico cuando no se tiene un algoritmo. No es solo el programa
sino las definiciones originales y los algoritmos los que deben desarrollarse. En general,
cuando encaramos la tarea de escribir un programa para resolver un problema no hay razón
para buscar una solución recursiva. La mayoría de los problemas pueden resolverse de una
manera directa usando métodos no recursivos. Sin embargo, otros pueden resolverse de una
manera más lógica y elegante mediante la recursión.
Algoritmos Ejemplos de algoritmos recursivos
Una técnica común de resolución de problemas es la división de un problema en varios

problemas 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 los cuales el algoritmo se llama a sí mismo repetidamente,
procurando simplificar o reducir el problema en cada llamada, hasta llegar a un caso trivial
de solución directa.
Para comprender el funcionamiento de un algoritmo recursivo es fundamental conocer cómo

funciona la pila de llamadas de un programa en ejecución.
El ejemplo más típico de algoritmo recursivo es el de una función para calcular la factorial
de un número. La 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 la factorial de un número es equivalente al producto de dicho número por la factorial del
número precedente: factorial (3) = 3 * factorial (2) podemos plantear una implementación
recursiva: función factorial(n) si n = 1 d sino ev ol ve r 1 devolver n * factorial (n – 1) fin
si fin función 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.
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.
La pila de llamadas
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. Cuando en un
punto concreto de un programa se llama a una función -sea recursiva o no- se reserva espacio
en la pila para la siguiente información
Llamadas recursivas
Una vez visto el funcionamiento básico de la pila de llamadas de un programa, podemos

estudiar el uso de la pila en una función recursiva con un ejemplo. Para ello, seguiremos con
el ejemplo del cálculo de la factorial de un número. El siguiente esquema muestra el uso de
la pila que resulta de hacer una llamada a la función factorial
Listas enlazadas
En una estructura del tipo lista enlazada cada nodo contiene una referencia al siguiente nodo
(alternativamente es posible que contenga una referencia al nodo anterior, en las listas
doblemente encadenadas), y un conjunto de atributos extra específicos del nodo en cuestión
Una función que opere de forma recursiva sobre una lista enlazada, deberá procesar el nodo
actual y pasar como parámetro el nodo siguiente. La condición de salida en este caso se dará
cuando lleguemos a un nodo de valor null, que indicará el final de la lista

Universidad Andina Del Cusco

Cargado por

Copyright:

Formatos disponibles

Universidad Andina Del Cusco

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Universidad Andina Del Cusco

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD ANDINA DEL CUSCO

“Año del Bicentenario del Perú: 200 años de

ASIGNATURA: Algoritmo y Lenguaje de programación estructurada

DOCENTES: Ing. LUIS ENRIQUE DEL CARPIO CUENTAS

ALUMNO: Yarahuaman Ybarra, Martin Donato 020200719f

Algoritmos Ejemplos de algoritmos recursivos

Una técnica común de resolución de problemas es la división de un problema en varios

Para comprender el funcionamiento de un algoritmo recursivo es fundamental conocer cómo

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

Una vez visto el funcionamiento básico de la pila de llamadas de un programa, podemos

También podría gustarte