República Bolivariana de VenezuelaMinisterio del Poder Popular de la Educación Superior

Colegio Universitario Francisco de MirandaAsignatura: Programación I

Alumnos:

Maykel Ramírez C.I .16.027.309Alejandro Estrada C.I .19.396.690

Resumen

La recursividad (recursión) es una técnica de programación elemental que permite que una función pueda llamarse asimismo desde la misma función. Se puede utilizar

la recursividad como una alternativa a la iteración. La recursividad es una herramienta poderosa e importante en la resolución de problemas en programación. Una solución recursiva es normalmente menos eficiente en términos de tiempo de computadora que una solución iterativa debido a las operaciones auxiliares que llevan consigo las llamadas suplementarias a las funciones: sin embargo, en muchas circunstancias el uso de la recursión permite a los programadores especificar las soluciones naturales, más lógicas, elegantes, sencillas, que serían, en caso contrario difícil de resolver.

La naturaleza de la recursividad es aquella que se llama así misma bien directamente, o bien a través de otra función. En matemática existen numerosas funciones que tienen carácter recursivo de igual modo numerosas circunstancias y situaciones de la vida ordinaria tienen carácter recursivo. Una función que contiene sentencias entre las que se encuentran al menos una que llama a la propia función se dice que es recursiva.

Cabe destacar, que una función en el campo de la informática son subprogramas o subrutina que realizan una tarea específica y devuelve un valor, del mismo modo, se puede decir que esta subrutina o subprograma forma parte del programa o rutina principal.

RECURSIVIDADRECURSIVIDAD

Definición de RecursividadDefinición de RecursividadUn procedimiento o función se dice recursivo si durante su ejecución se invocaUn procedimiento o función se dice recursivo si durante su ejecución se invoca directa o indirectamente asimismo. Esta invocación depende al menos de unadirecta o indirectamente asimismo. Esta invocación depende al menos de una condición que actúa como condición que actúa como condición de cortecondición de corte que provoca la finalización de la que provoca la finalización de la recursión.recursión.

•• Un algoritmo típico que conduce a una implementación recursiva es el cálculoUn algoritmo típico que conduce a una implementación recursiva es el cálculo del factorial de un número. El factorial de del factorial de un número. El factorial de n n (n ! ).(n ! ).

•• n! = n * (n-1) * (n-2) * _. . * 3 * 2 * In! = n * (n-1) * (n-2) * _. . * 3 * 2 * I

•• 1! = 1 1! = 1

•• 2! = 1 x 2 = 2 2! = 1 x 2 = 2

•• 3! = 1 x 2 x 3 = 6 3! = 1 x 2 x 3 = 6

•• 4! = 1 x 2 x 3 x 4 = 24 4! = 1 x 2 x 3 x 4 = 24

•• 5! = 1 x 2 x 3 x 4 x 5 = 120 5! = 1 x 2 x 3 x 4 x 5 = 120

•• 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720

•• En consecuencia, el factorial de 4 es igual a 4*3*2* En consecuencia, el factorial de 4 es igual a 4*3*2* 1, 1, el factorial de 3 esel factorial de 3 es igual a 3*2* I. igual a 3*2* I. Así Así pues, el factorial de 4 es igual a 4 veces el factorial de 3. pues, el factorial de 4 es igual a 4 veces el factorial de 3.

Otro ejemplo clásico de recursión es la Otro ejemplo clásico de recursión es la serie de fibonaciserie de fibonaci, cuya definición es la , cuya definición es la siguiente:siguiente:

fibonaci(1) = 1;fibonaci(1) = 1;fibonaci(2) = 1;fibonaci(2) = 1;fibonaci(3) = fibonaci(2) + fibonaci(1);fibonaci(3) = fibonaci(2) + fibonaci(1);fibonaci(4) = fibonaci(3) + fibonaci(2);fibonaci(4) = fibonaci(3) + fibonaci(2);

Es decir la número de fibonaci de 1 y 2 es 1 en ambos casos, el número fibonaciEs decir la número de fibonaci de 1 y 2 es 1 en ambos casos, el número fibonaci de 3 es la suma del fibonaci de 2 y 1, el número fibonaci de 4 es la suma del de 3 es la suma del fibonaci de 2 y 1, el número fibonaci de 4 es la suma del fibonaci de 3 y 2, y así en forma sucesiva, la definición sería:fibonaci de 3 y 2, y así en forma sucesiva, la definición sería:

fibonaci(n) = fibonaci(n-1) + fibonaci(n-2)fibonaci(n) = fibonaci(n-1) + fibonaci(n-2)

Implementado esto en forma recursiva quedaría como:Implementado esto en forma recursiva quedaría como:

La función La función factorialfactorial, escrita de forma recursiva, sería como sigue:, escrita de forma recursiva, sería como sigue:

unsigned long factorial(unsigned long numero)unsigned long factorial(unsigned long numero){{     if ( numero == 1 || numero == 0 )if ( numero == 1 || numero == 0 )         return 1; return 1;

  /* El else no hace falta, ya que es obvio *//* El else no hace falta, ya que es obvio */     return numero * factorial(numero-1);return numero * factorial(numero-1);

}}

unsigned long fibonaci(unsigned long numero)unsigned long fibonaci(unsigned long numero){{     if ( numero == 1 || numero == 2 )if ( numero == 1 || numero == 2 )         return 1; return 1;

     /* El else no hace falta, ya que es obvio *//* El else no hace falta, ya que es obvio */     return fibonaci(numero-1) + fibonaci(numero-2);return fibonaci(numero-1) + fibonaci(numero-2);}}

Ámbito de aplicaciónÁmbito de aplicación

•• General.General.

•• Problemas cuya solución se puede hallar solucionando el mismo problema peroProblemas cuya solución se puede hallar solucionando el mismo problema pero con un caso de menor tamaño.con un caso de menor tamaño.

•••• Razones de usoRazones de uso ::

•• Problemas más fáciles de resolver que con estructuras iterativas.Problemas más fáciles de resolver que con estructuras iterativas.

•• Soluciones elegantes.Soluciones elegantes.

•• Soluciones más simples.Soluciones más simples.

•• Por ejemplo, la función factorial podría implementarse:Por ejemplo, la función factorial podría implementarse:int factorial( int n)int factorial( int n){{

if (n<2)if (n<2){{

return 1;return 1;}}elseelse

{{ return n*factorial(n-1); return n*factorial(n-1);}}

}} Ventajas y desventajas de la recursividadVentajas y desventajas de la recursividad

VentajasVentajas: :

•• No es necesario definir la secuencia de pasos exacta para resolver el problema.No es necesario definir la secuencia de pasos exacta para resolver el problema.

•• Soluciones simples, claras.Soluciones simples, claras.

•• Soluciones elegantes.Soluciones elegantes.

•• Soluciones a problemas complejos.Soluciones a problemas complejos.

Desventajas: Desventajas:

–– Podría ser menos eficiente.Podría ser menos eficiente.–– Sobrecarga asociada con las llamadas a subalgoritmosSobrecarga asociada con las llamadas a subalgoritmos

•• Una simple llamada Una simple llamada puedepuede generar un gran número de llamadas generar un gran número de llamadas recursivas.recursivas. (Fact(n) (Fact(n) generagenera n n llamadasllamadas recursivas) recursivas)

•• ¿La claridad compensa la sobrecarga?¿La claridad compensa la sobrecarga?

•• El valor de la recursividad reside en el hecho de que se puede usar para resolverEl valor de la recursividad reside en el hecho de que se puede usar para resolver problemas sin fácil solución iterativa.problemas sin fácil solución iterativa.

–– La ineficiencia inherente de algunos algoritmos recursivos.La ineficiencia inherente de algunos algoritmos recursivos.

Diseño de algoritmos recursivosDiseño de algoritmos recursivos

•• Para resolver un problema, el primer paso será la identificación de un algoritmoPara resolver un problema, el primer paso será la identificación de un algoritmo recursivo, es decir, descomponer el problema de forma que su solución quederecursivo, es decir, descomponer el problema de forma que su solución quede definida en función de ella misma pero para un tamaño menor y la tarea adefinida en función de ella misma pero para un tamaño menor y la tarea a realizar para un caso simple.realizar para un caso simple.

Tendremos que diseñar: casos base, casos generales y la solución en términosTendremos que diseñar: casos base, casos generales y la solución en términos de ellos.de ellos.

•• Casos base: Son los casos del problema que resuelve con un segmento deCasos base: Son los casos del problema que resuelve con un segmento de código sin recursividad.código sin recursividad.

•• El número y forma de los casos base son hasta cierto punto arbitrarios. LaEl número y forma de los casos base son hasta cierto punto arbitrarios. La solución será mejor cuanto más simple y eficiente resulte el conjunto de casossolución será mejor cuanto más simple y eficiente resulte el conjunto de casos seleccionados.seleccionados.

•• Casos generales: Si el problema es suficientemente complejo, la solución seCasos generales: Si el problema es suficientemente complejo, la solución se expresa, de forma recursiva, como la unión deexpresa, de forma recursiva, como la unión de

1.1. La solución de uno o más subproblemas de igual naturaleza pero menorLa solución de uno o más subproblemas de igual naturaleza pero menor tamaño).tamaño).

2.2. Un conjunto de pasos adicionales. Estos pasos junto con las soluciones a losUn conjunto de pasos adicionales. Estos pasos junto con las soluciones a los subproblemas componen la solución al problema general que queremossubproblemas componen la solución al problema general que queremos resolver.resolver.

Escritura de programas recursivosEscritura de programas recursivos

•• 1.-Obtención de una definición exacta del problema1.-Obtención de una definición exacta del problema

•• 2.-Determinar el tamaño del problema completo que hay que resolver 2.-Determinar el tamaño del problema completo que hay que resolver Parámetros en la llamada inicialParámetros en la llamada inicial

•• 3.-Resolver el(los) casos bases o triviales (no recursivos).3.-Resolver el(los) casos bases o triviales (no recursivos).

•• 4.-Resolver el caso general en términos de un caso más pequeño (llamada 4.-Resolver el caso general en términos de un caso más pequeño (llamada recursiva).recursiva).

Ejemplo 1Ejemplo 1Realizar el algoritmo de la función factorial.Realizar el algoritmo de la función factorial.La implementación de la función recursiva factorial La implementación de la función recursiva factorial es:es:

double factorial (int número)double factorial (int número){{

if (numero > 1)if (numero > 1)return número * factorial (numero-1);return número * factorial (numero-1);

return 1;return 1;}}

Ejemplo 2Ejemplo 2Contar valores de 1 a 10 de modo recursivo.Contar valores de 1 a 10 de modo recursivo.#include <stdio.h>#include <stdio.h>void contar (int cima);void contar (int cima);int main()int main(){{

contar(10);contar(10);

return O;return O;}}void contar (int cima)void contar (int cima){{

if (cima > 1)if (cima > 1)contar (cima-1);contar (cima-1);

printf (“%d ”printf (“%d ”, , cima) ;cima) ;}}

ANEXOS