Recursividad
Realizado por: M.S.C. Ivette Hdez. Dávila
Introducción
¿Alguna vez has visto un juego de muñecas rusas? Al principio, solo ves una figurilla, generalmente de madera pintada. Puedes quitar la mitad de arriba de la primera muñeca, ¿y qué ves adentro? ¡Otra muñeca rusa, un poco más pequeña! Puedes quitar esa muñeca y separar sus mitades superior e inferior. Y ves, una vez más, otra muñeca más pequeña. Y puedes continuar. Eventualmente encontrarás la muñeca rusa más pequeña. Es de una sola pieza, así que no se abre.
Contenido
7 · Elementos
1 · ¿Qué es la recursividad?
8 · Ejemplo
2 · ¿Cuándo utilizarla?
9 · Video
3 · Función recursiva
10 · Ejercicios
4 · Reglas
5 · Recursión vs Iteración
6 · Tipos de recursividad
¿Qué es la recursividad en programación?
La recursividad en Python
La recursividad es un concepto que se indica cuando una función se llama a si misma. Cuando creamos una función recursiva debemos tener en cuenta que este tiene que terminar por lo que dentro de la función debemos asegurarnos de que no se está llamando a si mismo todo el rato, Lo que quiere decir que el ciclo es finito.
Una función recursiva es aquella que está definida en función de sí misma, por lo que se llama repetidamente a sí misma hasta llegar a un punto de salida.
Cualquier función recursiva tiene dos secciones de código claramente divididas:
- Por un lado tenemos la sección en la que la función se llama a sí misma.
- Por otro lado, tiene que existir siempre una condición en la que la función retorna sin volver a llamarse.
¿Cuándo utilizar recursividad?
¿Cuándo utilizar la recursidad?
Aun así, la gran mayoría de las veces, utilizamos recursividad para algoritmos de búsqueda u ordenación. Se denomina caso base a la condición de terminación de la recursividad.
Podemos utilizar recursividad para reemplazar cualquier tipo de bucle. A pesar de ello en el mundo laboral no se utiliza demasiado, debido a que un error puede ser trágico en la memoria, así como tener una lista con millones de datos, puede hacer que utiliza mucha memoria.
¿Cómo escribir una función recursiva?
Función recursiva
Para resolver un problema, resuelve un subproblema que sea una instancia más pequeña del mismo problema, y después usa la solución de esa instancia más pequeña para resolver el problema original. Para que un algoritmo recursivo funcione, los subproblemas más pequeños eventualmente deben llegar al caso base.
Reglas
Podemos extraer la idea de la recursión en dos reglas sencillas:
Regresemos a las muñecas rusas. Aunque no aparecen en ningún algoritmo, puedes ver que cada muñeca encierra a todas las muñecas más pequeñas (de manera análoga al caso recursivo), hasta que la muñeca más pequeña no encierra a ninguna otra (como el caso base).
Regla 1
Cada llamada recursiva debe ser sobre una instancia más pequeña del mismo problema, es decir, un subproblema más pequeño.
Regla 2
Las llamadas recursivas eventualmente deben alcanza un caso base, el cual se resuelve sin más recursividad.
Recursión vs Iteración
Recursión vs Iteración
La Iteración el ciclo termina cuando la condición del ciclo falla.
Iteración
Iteración significa repetir varias veces un proceso con la intención de alcanzar una meta deseada, objetivo o resultado.
La recursión termina cuando se reconoce el caso base.
Recursión
Cada repetición del proceso también se le denomina una "iteración", y los resultados de una iteración se utilizan como punto de partida para la siguiente iteración.
Tipos de Recursividad
Existen dos tipos de recursividad:
Directa
Cuando la función se llama a si misma.
Indirecta
Cuando la función A es llamada por una función B y la función B llama a la función A.
Elementos de los procesos recursivos
Caso general
Caso base
La condición
Es cuando los parámetros de entrada son suficientes grandes para separarlos y llamar la función nuevamente.
Es cuando los parámetros de entrada son suficientes pequeños para ser resueltos por otro método que no sea la recursiva.
La condición que siempre se busca, es el caso más pequeño, es decir, cuando los valores de los parámetros de entrada son suficientemente pequeños (decremento). Esta condición es buscada siempre para que se de el caso base y resolver el problema más pequeño de una manera que ya no se presente la recursividad.
Ejemplo
La función factorial
La función factorial es una fórmula matemática representada por el signo de exclamación “!”. En la fórmula Factorial se deben multiplicar todos los números enteros y positivos que hay entre el número que aparece en la fórmula y el número 1.
+Info
Video
10
Ejercicios
Ejercicio 1
Ejercicio 2
Potencia recursiva
Sucesión Fibonacci
Escribe una función rercursiva power(x, n) que regrese el valor de x^n.
(supón que n es un entero)
Empieza por escribir el caso base.
Implementar una función recursiva de la sucesión Fibonacci. Donde el caso base es: Las posiciones 0 y 1 son = 1. La posición 2 utiliza estos dos valores sumándolos.
La función factorial recursiva
¿Qué tienen que ver las muñecas rusas con los algoritmos?
Así como una muñeca rusa tienen una muñeca rusa más pequeña dentro de ella, que tiene una muñeca rusa aún más pequeña dentro de ella, hasta llegar a una muñeca rusa tan pequeña que ya no puede contener otra, vamos a ver cómo diseñar un algoritmo para resolver un problema de modo que resuelva una instancia más pequeña del mismo problema, a menos que el problema sea tan pequeño que lo podamos resolver directamente. A esta técnica la llamamos recursividad.
recursión
Ivette Hdez. Dávila
Created on July 10, 2023
Funciones recursivos
Start designing with a free template
Discover more than 1500 professional designs like these:
View
Mobile App Dossier
View
Color Shapes Dossier
View
Notes Dossier
View
Futuristic Tech Dossier
View
Crowdfunding Campaign
View
Company Dossier
View
Economy Dossier
Explore all templates
Transcript
Recursividad
Realizado por: M.S.C. Ivette Hdez. Dávila
Introducción
¿Alguna vez has visto un juego de muñecas rusas? Al principio, solo ves una figurilla, generalmente de madera pintada. Puedes quitar la mitad de arriba de la primera muñeca, ¿y qué ves adentro? ¡Otra muñeca rusa, un poco más pequeña! Puedes quitar esa muñeca y separar sus mitades superior e inferior. Y ves, una vez más, otra muñeca más pequeña. Y puedes continuar. Eventualmente encontrarás la muñeca rusa más pequeña. Es de una sola pieza, así que no se abre.
Contenido
7 · Elementos
1 · ¿Qué es la recursividad?
8 · Ejemplo
2 · ¿Cuándo utilizarla?
9 · Video
3 · Función recursiva
10 · Ejercicios
4 · Reglas
5 · Recursión vs Iteración
6 · Tipos de recursividad
¿Qué es la recursividad en programación?
La recursividad en Python
La recursividad es un concepto que se indica cuando una función se llama a si misma. Cuando creamos una función recursiva debemos tener en cuenta que este tiene que terminar por lo que dentro de la función debemos asegurarnos de que no se está llamando a si mismo todo el rato, Lo que quiere decir que el ciclo es finito.
Una función recursiva es aquella que está definida en función de sí misma, por lo que se llama repetidamente a sí misma hasta llegar a un punto de salida. Cualquier función recursiva tiene dos secciones de código claramente divididas:
¿Cuándo utilizar recursividad?
¿Cuándo utilizar la recursidad?
Aun así, la gran mayoría de las veces, utilizamos recursividad para algoritmos de búsqueda u ordenación. Se denomina caso base a la condición de terminación de la recursividad.
Podemos utilizar recursividad para reemplazar cualquier tipo de bucle. A pesar de ello en el mundo laboral no se utiliza demasiado, debido a que un error puede ser trágico en la memoria, así como tener una lista con millones de datos, puede hacer que utiliza mucha memoria.
¿Cómo escribir una función recursiva?
Función recursiva
Para resolver un problema, resuelve un subproblema que sea una instancia más pequeña del mismo problema, y después usa la solución de esa instancia más pequeña para resolver el problema original. Para que un algoritmo recursivo funcione, los subproblemas más pequeños eventualmente deben llegar al caso base.
Reglas
Podemos extraer la idea de la recursión en dos reglas sencillas:
Regresemos a las muñecas rusas. Aunque no aparecen en ningún algoritmo, puedes ver que cada muñeca encierra a todas las muñecas más pequeñas (de manera análoga al caso recursivo), hasta que la muñeca más pequeña no encierra a ninguna otra (como el caso base).
Regla 1
Cada llamada recursiva debe ser sobre una instancia más pequeña del mismo problema, es decir, un subproblema más pequeño.
Regla 2
Las llamadas recursivas eventualmente deben alcanza un caso base, el cual se resuelve sin más recursividad.
Recursión vs Iteración
Recursión vs Iteración
La Iteración el ciclo termina cuando la condición del ciclo falla.
Iteración
Iteración significa repetir varias veces un proceso con la intención de alcanzar una meta deseada, objetivo o resultado.
La recursión termina cuando se reconoce el caso base.
Recursión
Cada repetición del proceso también se le denomina una "iteración", y los resultados de una iteración se utilizan como punto de partida para la siguiente iteración.
Tipos de Recursividad
Existen dos tipos de recursividad:
Directa
Cuando la función se llama a si misma.
Indirecta
Cuando la función A es llamada por una función B y la función B llama a la función A.
Elementos de los procesos recursivos
Caso general
Caso base
La condición
Es cuando los parámetros de entrada son suficientes grandes para separarlos y llamar la función nuevamente.
Es cuando los parámetros de entrada son suficientes pequeños para ser resueltos por otro método que no sea la recursiva.
La condición que siempre se busca, es el caso más pequeño, es decir, cuando los valores de los parámetros de entrada son suficientemente pequeños (decremento). Esta condición es buscada siempre para que se de el caso base y resolver el problema más pequeño de una manera que ya no se presente la recursividad.
Ejemplo
La función factorial
La función factorial es una fórmula matemática representada por el signo de exclamación “!”. En la fórmula Factorial se deben multiplicar todos los números enteros y positivos que hay entre el número que aparece en la fórmula y el número 1.
+Info
Video
10
Ejercicios
Ejercicio 1
Ejercicio 2
Potencia recursiva
Sucesión Fibonacci
Escribe una función rercursiva power(x, n) que regrese el valor de x^n. (supón que n es un entero) Empieza por escribir el caso base.
Implementar una función recursiva de la sucesión Fibonacci. Donde el caso base es: Las posiciones 0 y 1 son = 1. La posición 2 utiliza estos dos valores sumándolos.
La función factorial recursiva
¿Qué tienen que ver las muñecas rusas con los algoritmos?
Así como una muñeca rusa tienen una muñeca rusa más pequeña dentro de ella, que tiene una muñeca rusa aún más pequeña dentro de ella, hasta llegar a una muñeca rusa tan pequeña que ya no puede contener otra, vamos a ver cómo diseñar un algoritmo para resolver un problema de modo que resuelva una instancia más pequeña del mismo problema, a menos que el problema sea tan pequeño que lo podamos resolver directamente. A esta técnica la llamamos recursividad.