Programación I Capítulo 3 Recursividad

Fundamentos de Programación
Recursividad
Dra. Tania Calle Jiménez
2021B
tania.calle@epn.edu.ec
Funciones: Recursividad
Hasta el momento, las únicas funciones que

se ha estudiado han sido llamadas desde
otra función; pero es posible crear funciones
que puedan llamarse a sí mismas, estas son
llamadas: funciones recursivas.
• Se dice que una función es recursiva cuando se
define en función de si misma.
• No todas la funciones pueden llamarse a si
mismas, sino que deben estar diseñadas
especialmente para que sean recursivas, de otro
modo podrían conducir a bucles infinitos, o a que
el programa termine inadecuadamente.
• Tampoco todos los lenguajes de programación
permiten usar recursividad.
• C++ permite la recursividad. Cada vez que se
llama a una función, se crea un juego de variables
locales, de este modo, si la función hace una
llamada a si misma, se guardan sus variables y
parámetros, usando la pila, y la nueva instancia
de la función trabajará con su propia copia de las
variables locales. Cuando esta segunda instancia
de la función retorna, recupera las variables y los
parámetros de la pila y continua la ejecución en
el punto en que había sido llamada.
• Por ejemplo:
• Podríamos crear una función recursiva para
calcular el factorial de un número entero.
• El factorial se simboliza como n!, se lee como
"n factorial", y la definición es:
• n! = n * (n – 1)!
Forma iteractiva
• int factorial(int n)
• { int i, fact = 1;
• for (i=2; i<=n; i++)
• fact = fact * i;
• return(fact); }
• /* Función recursiva para cálculo de factoriales */
• int factorial(int n)
• { if(n < 0)
• return 0;
• else if(n > 1)
• return n*factorial(n-1); /* Recursividad */
• return 1; /* Condición de terminación, n == 1 */ }
• Veamos paso a paso, lo que pasa cuando se
ejecuta esta función, por ejemplo: factorial(4):
– 1a Instancia
n=4
n>1
salida ← 4 * factorial(3) (Guarda el valor de n = 4)
• 2a Instancia
n>1
salida ← 3*factorial(2) (Guarda el valor de n = 3)
– 3a Instancia
n>1
salida ← 2*factorial(1) (Guarda el valor de n = 2)
» 4a Instancia
n == 1 → retorna 1
– 3a Instancia
(recupera n=2 de la pila) retorna 1*2=2
• 2a instancia
– 1a instancia
Valor de retorno → 24
• Hay algunas limitaciones:
– No es posible calcular el factorial de números
negativos, no está definido.
– El factorial de cero es 1.
– De modo que una función bien hecha para cálculo
de factoriales debería incluir un control para esos
casos:
• Aunque la función factorial es un buen ejemplo
para demostrar cómo funciona una función
recursiva, la recursividad no es un buen modo
de resolver esta función, que sería más sencilla
y rápida con un simple bucle for.
• La recursividad consume muchos recursos de
memoria y tiempo de ejecución, y se debe
aplicar a funciones que realmente le saquen
partido.
Ventajas de la Recursión
• Soluciones simples, claras.
• Soluciones elegantes.
• Soluciones a problemas complejos.
Desventajas de la Recursión
• Sobrecarga asociada con las llamadas a subalgoritmos

• Una simple llamada puede generar un gran numero de
llamadas recursivas. (Fact(n) genera n llamadas
recursivas)
• ¿La claridad compensa la sobrecarga?
• El valor de la recursividad reside en el hecho de que se
puede usar para resolver problemas sin fácil solución
iterativa.
• La ineficiencia inherente de algunos algoritmos
recursivos.
• LA RECURSIVIDAD SE DEBE USAR
CUANDO SEA REALMENTE
NECESARIA, ES DECIR, CUANDO NO
EXISTA UNA SOLUCIÓN ITERATIVA
SIMPLE.
Depuración
Ejemplos
• Contar valores de 1 a 10 de modo recursivo.
• #include <stdio.h>
• void contar(int cima);
• int main()
• {
• contar(10);
• return 0;
• }
• void contar(int cima)
• {
• if (cima > 1)
• contar(cima-1);
• printf ("%d ", cima) ; }
Función para calcular módulo
• El operador binario módulo obtiene el resto o

residuo de la división de dos números enteros.
• Es bastante sencillo definir en forma recursiva
la operación m mod n. La idea es ir restando el
divisor del dividendo y calculando de nuevo el
módulo, pues el resultado es el mismo. La
recursividad se detiene cuando el divisor es
mayor que el dividendo. En ese caso el
resultado es el dividendo. La definición sería:
A partir de esta definición, se puede escribir una
función en C que calcule m mod n, con m y n como
los parámetros de la función. En el siguiente ejemplo
se presenta esta función, junto con un programa de
prueba que pide dos números enteros al usuario,
calcula la operación y muestra en pantalla el
resultado.
Módulo de dos números
• int modulo(int m, int n);
• void main()
• { int m, n; /* Se solicita al usuario los valores de m y n */
• printf("Ingrese el valor de m: ");
• scanf("%d", &m);
• printf("Ingrese el valor de n: ");
• scanf("%d", &n);
• /* Imprime el resultado de m mod n, empleando la funcion modulo */
• printf("%d mod %d es: %d\n", m, n, modulo(m,n)); }
• int modulo(int m, int n)

• { if (m < n) return(m);
• else return( modulo( (m-n) , n) );
• /* Llamado recursivo */ }
• Determinar si un número entero positivo es
par o impar; con dos funciones que se llaman
mutuamente: recursividad indirecta.
• int par(int n) ;
• int impar(int n);
• int main (void)

• { int n;
• do{/* Entrada: entero > O */
• printf ("\nEntero >0: " ) ;
• scanf ("%d", &n) ;
• } while (n<=0);
• /* Llamada a la funcion par() */
• if (par(n))
• printf ( "El numero %d es par", n) ;
• else printf ( "El numero %d es impar", n) ;
• return 0; }
• int par(int n)
• { if (n == 0)
• return 1; /* es par */
• else
• return impar(n-1); }
• int impar(int n)
• { if (n == 0)
• return 0; /* es impar */
• else
• return par(n-1); }
• La función par ( ) llama a la función impar ( ) ,
ésta a su vez llama a la función par ( ) . La
condición para terminar de hacer llamadas es
que n sea cero; el cero se considera par.
• De manera similar a como se definió
recursivamente el operador módulo es posible
definir el operador para división entera, es decir,
división sobre operandos enteros y cuyo
resultado es entero (se ignoran los decimales).
• Como ejercicio la definición recursiva de este
operador y la implementación de la función en C
correspondiente. Como programa de prueba
puede emplearse el mismo que se empleó para el
módulo con unos pocos cambios.
• 1.- Programa en C que calcula el producto de dos
números de forma recursiva. Los números a multiplicar
se leen por teclado.
• 2.- Programa en C que calcula la división de dos

números de forma recursiva. Los números a dividir se
leen por teclado.
• 3. función recursiva que encuentre el número mayor

de una serie de números.
• 4.- Calcular el máximo común divisor de dos
números de forma recursiva en c.
• 5.- Convertir Decimal a Binario de forma

recursiva.

Programación I Capítulo 3 Recursividad

Cargado por

Copyright:

Formatos disponibles

Programación I Capítulo 3 Recursividad

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

Programación I Capítulo 3 Recursividad

Cargado por

Copyright:

Formatos disponibles

Fundamentos de Programación

Hasta el momento, las únicas funciones que

• Sobrecarga asociada con las llamadas a subalgoritmos

• El operador binario módulo obtiene el resto o

• int modulo(int m, int n)

• int main (void)

• 2.- Programa en C que calcula la división de dos

• 3. función recursiva que encuentre el número mayor

• 5.- Convertir Decimal a Binario de forma

También podría gustarte