Monografías Plus      Agregar a favoritos      Ayuda      Português      Ingles     

Introducción a la recursión (ppt)

Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com
Concepto de recursión Recursión (recursividad, recurrencia) Definición recursiva: En la definición aparece lo que se define Factorial(N) = N x Factorial(N-1) (N >= 0)
Monografias.com
Definiciones recursivas Factorial(N) = N x Factorial(N-1) El factorial se define en función de sí mismo Los programas no pueden manejar la recursión infinita La definición recursiva debe adjuntar uno o más casos base Caso base: aquel en el que no se utiliza la definición recursiva Proporcionan puntos finales de cálculo: El valor de N se va aproximando al valor del caso base (0) N x Factorial(N-1) si N > 0 Caso recursivo (inducción) Factorial(N) 1 si N = 0 Caso base (o de parada)
Monografias.com
Algoritmos recursivos Funciones recursivas Una función puede implementar un algoritmo recursivo La función se llamará a sí misma si no se ha llegado al caso base long long int factorial(int n) { long long int resultado; if (n == 0) { // Caso base resultado = 1; } else { resultado = n * factorial(n - 1); } return resultado; } (Gp:) N x Factorial(N-1) si N > 0 (Gp:) Factorial(N) (Gp:) 1 si N = 0
Monografias.com
Algoritmos recursivos Funciones recursivas long long int factorial(int n) { long long int resultado; if (n == 0) { // Caso base resultado = 1; } else { resultado = n * factorial(n - 1); } return resultado; } factorial(5) ? 5 x factorial(4) ? 5 x 4 x factorial(3) ? 5 x 4 x 3 x factorial(2) ? 5 x 4 x 3 x 2 x factorial(1) ? 5 x 4 x 3 x 2 x 1 x factorial(0) ? 5 x 4 x 3 x 2 x 1 x 1 ? 120 (Gp:) Caso base
Monografias.com
Algoritmos recursivos Diseño de funciones recursivas Una función recursiva debe satisfacer tres condiciones: Caso(s) base: Debe haber al menos un caso base de parada Inducción: Paso recursivo que provoca una llamada recursiva Debe ser correcto para distintos parámetros de entrada Convergencia: Cada paso recursivo debe acercar a un caso base Se describe el problema en términos de problemas más sencillos Función factorial(): tiene caso base (N = 0), siendo correcta para N es correcta para N+1 (inducción) y se acerca cada vez más al caso base (N-1 está más cerca de 0 que N) (Gp:) N x Factorial(N-1) si N > 0 (Gp:) Factorial(N) (Gp:) 1 si N = 0
Monografias.com
Modelo de ejecución long long int factorial(int n) { long long int resultado; if (n == 0) { // Caso base resultado = 1; } else { resultado = n * factorial(n - 1); } return resultado; } Cada llamada recursiva fuerza una nueva ejecución de la función Cada llamada utiliza sus propios parámetros por valor y variables locales (n y resultado en este caso) En las llamadas a la función se utiliza la pila del sistema para mantener los datos locales y la dirección de vuelta
Monografias.com
La pila del sistema (stack) Regiones de memoria que distingue el sistema operativo: (Gp:) Llamadas a subprogramas (Gp:) Memoria dinámica (Tema 9) (Gp:) Memoria principal
Monografias.com
La pila del sistema (stack) Mantiene los datos locales de la función y la dirección de vuelta Estructura de tipo pila: lista LIFO (last-in first-out) El último que entra es el primero que sale: Entra 4 Entra 7 Entra 2 Sale 2
Monografias.com
La pila y las llamadas a función Datos locales y direcciones de vuelta ... int funcB(int x) { ... return x; } int funcA(int a) { int b; ... b = funcB(a); ... return b; } int main() { ... cout << funcA(4); ... Pila (Gp:) Llamada a función: Entra la dirección de vuelta
Monografias.com
Datos locales y direcciones de vuelta ... int funcB(int x) { ... return x; } int funcA(int a) { int b; ... b = funcB(a); ... return b; } int main() { ... cout << funcA(4); ... La pila y las llamadas a función Pila (Gp:) Entrada en la función: Se alojan los datos locales
Monografias.com
Datos locales y direcciones de vuelta ... int funcB(int x) { ... return x; } int funcA(int a) { int b; ... b = funcB(a); ... return b; } int main() { ... cout << funcA(4); ... La pila y las llamadas a función Pila (Gp:) Llamada a función: Entra la dirección de vuelta
Monografias.com
Datos locales y direcciones de vuelta ... int funcB(int x) { ... return x; } int funcA(int a) { int b; ... b = funcB(a); ... return b; } int main() { ... cout << funcA(4); ... La pila y las llamadas a función Pila (Gp:) Entrada en la función: Se alojan los datos locales
Monografias.com
Datos locales y direcciones de vuelta ... int funcB(int x) { ... return x; } int funcA(int a) { int b; ... b = funcB(a); ... return b; } int main() { ... cout << funcA(4); ... La pila y las llamadas a función Pila (Gp:) Vuelta de la función: Se eliminan los datos locales
Monografias.com
Datos locales y direcciones de vuelta ... int funcB(int x) { ... return x; } int funcA(int a) { int b; ... b = funcB(a); ... return b; } int main() { ... cout << funcA(4); ... La pila y las llamadas a función Pila (Gp:) Vuelta de la función: Sale la dirección de vuelta
Monografias.com
Datos locales y direcciones de vuelta ... int funcB(int x) { ... return x; } int funcA(int a) { int b; ... b = funcB(a); ... return b; } int main() { ... cout << funcA(4); ... La pila y las llamadas a función Pila (Gp:) La ejecución continúa en esa dirección
Monografias.com
Recursión simple Sólo hay una llamada recursiva Ejemplo: Cálculo del factorial de un número entero positivo long long int factorial(int n) { long long int resultado; if (n == 0) { // Caso base resultado = 1; } else { resultado = n * factorial(n - 1); } return resultado; } (Gp:) Una sola llamada recursiva
Partes: 1, 2

Página siguiente 

Comentarios


Trabajos relacionados

Ver mas trabajos de Otros

 
 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.