Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 6: Algoritmos recursivos- Recursividad
- La función factorial
- Desafío: factorial iterativo
- Factorial recursivo
- Desafío: factorial recursivo
- Propiedades de los algoritmos recursivos
- Usar recursividad para determinar si una palabra es un palíndromo o no
- Desafío: ¿una cadena de caracteres es un palíndromo?
- Calcular potencias de un número
- Desafío: potencias recursivas
- Recursividad múltiple con el triángulo de Sierpinski
- Mejorar la eficiencia de las funciones recursivas
- Proyecto: arte recursivo
© 2023 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
Recursividad múltiple con el triángulo de Sierpinski
Hasta ahora, los ejemplos de recursividad que hemos visto requieren que hagas una llamada recursiva cada vez. Pero a veces necesitas hacer mútiples llamadas recursivas. Aquí hay un buen ejemplo, una construcción matemática que es un fractal conocido como un triágulo de Sierpinski:
Como puedes ver, es una colección de cuadritos dibujados en un patrón particular dentro de una región cuadrada. Aquí está cómo dibujarlo. Comienza con la región completa cuadrada y divídela en cuatro secciones así:
Toma los tres cuadrados con una × en ellos (la parte superior izquierda, la parte superior derecha y la parte inferior derecha) y divídelas en cuatro secciones de la misma manera:
Continúa. Divide cada cuadrado con una × en cuatro secciones y pon una × en los cuadrados en la parte superior izquierda, superior derecha, superior e inferior derecha, pero nunca en la parte inferior izquierda.
Una vez los cuadrados se hagan lo suficientemente pequeños, deja de dividir. Si rellenas cada cuadrado con una × y te olvidas de todos los demás cuadrados, obtienes el triángulo de Sierpinski. Aquí está una vez más:
Para resumir, aquí está cómo dibujar un triángulo de Sierpinski en un cuadrado:
- Determina qué tan pequeño es el cuadrado. Si es suficientemente pequeño para ser un caso base, entonces simplemente rellena el cuadrado. Tú puedes escoger qué tan pequeño es "suficientemente pequeño".
- De lo contrario, divide el cuadrado en un cuadrado superior izquierdo, un cuadrado superior derecho, un cuadrado inferior derecho y un cuadrado inferior izquierdo. "Resuelve" tres subproblemas de manera recursiva:
- Dibuja un triángulo de Sierpinski en el cuadrado superior izquierdo.
- Dibuja un triángulo de Sierpinski en el cuadrado superior derecho.
- Dibuja un triángulo de Sierpinski en el cuadrado inferior derecho.
Date cuenta de que no solo necesitas hacer una, sino tres llamadas recursivas. Por eso consideramos dibujar un triángulo de Sierpinski para exhibir la recursividad múltiple.
Puedes escoger cualesquiera tres de los cuadrados en los cuales dibujar de manera recursiva triángulos de Sierpinski. El resultado simplemente saldrá rotado por algún múltiplo de 90 grados del dibujo anterior. (Si dibujas triángulos de Sierpinski de manera recursiva en cualquier otro número de cuadrados, no obtendrás un resultado interesante).
El siguiente programa dibuja un triángulo de Sierpinski. Intenta comentar y descomentar algunas de las llamadas recursivas para obtener triángulos rotados:
Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
- No entendi cual es mi error en el desafio anterior, Me pueden ayudar? :
var isEven = function(n) {
return n % 2 === 0;
};
var isOdd = function(n) {
return !isEven(n);
};
var power = function(x, n) {
println("Computing " + x + " raised to power " + n + ".");
// base case
if(n===0) {
return 1;
}
// recursive case: n is negative
if(n<0)
{
return (power(1/x,-n));
}
// recursive case: n is odd
if(isOdd(n)) {
return (power(x,n-1)*x);
}
// recursive case: n is even
if(isEven(n)) {
var y=power(x,n/2) ;
return y*y;
}
};
var displayPower = function(x, n) {
println(x + " to the " + n + " is " + power(x, n));
};
displayPower(3, 0);
Program.assertEqual(power(3, 0), 1);
displayPower(3, 1);
Program.assertEqual(power(3, 1), 3);
displayPower(3, 2);
Program.assertEqual(power(3, 2), 9);
displayPower(3, -1);
//Program.assertEqual(power(3, -1), 1/3);(2 votos) - se podria decir se que determina que en los cuadros la aplicacion determina para la obtencion de los triangulos las x para si poder obtener los triangulos.(1 voto)
- que es El triángulo de Sierpinski(1 voto)
- que es el triangulo de spirker(1 voto)
- Buenas,
Tal vez sea un poco extraño lo que estoy buscando
Hace hoy una semana encontré en la página de proyectos un proyecto que llevaba el nombre de "nuevo proyecto". Este nuevo proyecto trata sobre el triángulo de Sierpinsking, resulta que de todos los programas sobre dicho triángulo, este en particular, es de una simpleza en su desarrollo que me parece, por así decirlo, fantástico.
He intentado localizar dicho proyecto pero me ha sido imposible. Agracedería mucho que me ayudarán a encontrarlo o que hay qué hay que hacer para encontrarlo.
Gracias(1 voto)- fernando pasame todas las resputeas mi cnala se llama juandaiecdi(0 votos)
- que es El triángulo de Sierpinski?(0 votos)