algoritmos recursivos

Presentación

Algoritmos

Recursivos

EMPEZAR

Algoritmos

Recursividad

Integrantes del equipo

KEVIN FERNANDO LOPEZ OCHOA

STEPHANY MICHELL REVUELTA SOSA

OSCAR MARTINEZ MOYA

La conjetura de Collatz

Sea la siguiente operación, aplicable a cualquier número entero positivo: Si el número es par, se divide entre 2. Si el número es impar, se multiplica por 3 y se suma 1.

Al igual que el calculo del factorial, esta conjetura es recursiva ya que hace uso de su misma base durante todo el proceso sin importar los valores que existan.

Algoritmo recursivo

• Los algoritmos recursivos son una técnica de diseño de algoritmos en la que una función resuelve un problema al llamarse a sí misma con instancias más pequeñas del mismo problema.

• Permite descomponer problemas en subproblemas más pequeños y resolverlos de manera iterativa, lo que a menudo facilita la comprensión y la solución de problemas complejos en este campo.

Algotirmos recursivos

Estos algoritmos se basan en el concepto de recursión, que es un proceso en el cual una función se divide en tareas más pequeñas y se resuelve recursivamente hasta que se alcanza un caso base o condición de parada.

1.- Caso base y Caso recursivo

• Caso Base: Es una condición que indica cuándo debe detenerse la recursión. Cuando se cumple el caso base, la función recursiva deja de llamarse a sí misma y comienza a regresar resultados.

Caso Recursivo

Podemos extraer la idea de la recursión en dos reglas sencillas:

• Cada llamada recursiva debe ser sobre una instancia más pequeña del mismo problema, es decir, un subproblema más pequeño.
• Las llamdas recursivas eventualmente deben alcanzar un caso base, el cual se resuelve sin más recursividad.

Ejemplo visual de recursividad

ventajas de un algoritmo recursivo

• Son mas cercanos a la descripción matemática.
• Generalmente mas fáciles de analizar
• Se adaptan mejor a las estructuras de datos recursivas.
• Los algoritmos recursivos ofrecen soluciones estructuradas,
• modulares y elegantemente simples

Sección

¿cuándo es factible usar la recursividad?

Factible de utilizar recursividad

Para simplificar el código. • Cuando la estructura de datos es recursiva ejemplo : árboles

No factible utilizar recursividad

• Cuando los métodos usen arreglos largos. • Cuando el método cambia de manera impredecible de campos. • Cuando las iteraciones sean la mejor opción.

Sección

Ejemplo de un algoritmo recursivo

Calcular el factorial

Cantidad que resulta de la multiplicación de determinado número natural por todos los números naturales que le anteceden excluyendo el cero; se representa por n!

El factorial es un algoritmo recursivo?

Se dice que una función es recursiva cuando el cuerpo de la función utiliza a la propia función. Esto quiere decir que cuando el proceso en un algoritmo se esta repitiendo paara poder llegar a este resultado es un algoritmo recursivo, ya que tiene un inicio y un final, ademas de que el caso base se esta utilizando para poder resolver dicho algoritmo.

Recursividad aplicada a la vida cotidiana

• cuando doblas una carta para meterla en un sobre. Para doblarla, sigues el mismo proceso una y otra vez, dividiendo la carta en partes más pequeñas y doblando cada una de esas partes hasta que obtienes el tamaño adecuado para que quepa en el sobre.
• Este proceso de subdividir nos puede ver de una manera real un algoritmo recursivo
• Sigues repitiendo la misma acción de doblar la carta en cada paso hasta que la carta cabe por completo en el sobre o hasta que decides que no puedes doblarla más

JENGA

• estás construyendo una torre de bloques, como los juegos de Jenga. Cuando colocas un nuevo bloque en la torre, debes asegurarte de que esté alineado correctamente con los bloques anteriores para evitar que la torre se derrumbe. Para lograrlo, inspeccionas la torre desde arriba y ajustas la posición del nuevo bloque según sea necesario. Este proceso de alinear y verificar se repite recursivamente cada vez que agregas un nuevo bloque para mantener la estabilidad de la torre.

• Problema:
• Mantener la torre alineada

Sección

Ejemplo en un codigo

Sección

public static void main(String[] args) { int n = 3; int resultado = suma(n); System.out.println(resultado); } public static int suma(int n){ int valor; if(n == 1) { valor = 1; }else{ } valor =suma (n-1)+n; return valor; }

¡Gracias!

Ej. Calcula el factorial de 5

• Primero hay que tener la formula la cual es n(n-1)
• Luego hay que analizar cuales son los numeros anteriores al 5
• El factorial se representa como n!
• Por lo que 5!= 5x4x3x2x1
• Entonces esto quiere decir que el Factorial de 5 es igual a 120

Caso recursivo

Caso Recursivo Es la parte de la función que se llama a sí misma con instancias más pequeñas del problema. Esta llamada recursiva debe estar diseñada de manera que el problema se reduzca progresivamente hasta alcanzar el caso base.

Algoritmo

se llaman algoritmos el conjunto de instrucciones sistemáticas y previamente definidas que se utilizan para realizar una determinada tarea. Estas instrucciones están ordenadas y acotadas a manera de pasos a seguir para alcanzar un objetivo.

Entonces haciendo la aplicacion de esta regla Si usamos el numero 20 y aplicamos las bases de esta funcion

Nota: Esta regla es aplicable para cualquier numero, y siempre dara 1 al final

• 20 es par entonces se divide entre 2 dando como resultado 10
• 10 es par entonces se divide y da 5
• 5 es impar, multiplicamos por 3 y sumamos uno, dando como resultado 16
• 16/2=8
• 8/2=4
• 4/2=2
• 2/2=1
• Uno al ser impar se multiplica por 3 y se le suma 1, dando como resultado 4, entonces cae en el bucle de 4,2,1. Una vez llega al uno termina esta secuencia.

Recursividad

Se llama recursividad a un proceso mediante el que una función se llama a sí misma de forma repetida, hasta que se satisface alguna determinada condición.