Estructura de datos

TEMA 6

Recursividad

V1.1

Manuel Pereira González

Agenda
Introducción Ejemplos Factorial Invertir un Número Resolver Laberinto Cuándo utilizar Recursividad Algoritmos de Backtracking LasOcho Reinas Sudoku Resumen

1

Introducción
Poderosa herramienta de programación Alternativa a algoritmos iterativos Soluciones elegantes a problemas difíciles de resolver de otro modo Un métodoes recursivo si contiene invocaciones a sí mismo Una llamada a un método recursivo puede generar una o más invocaciones al mismo método, que a su ve genera otras, …

Introducción
Condiciones quedebe cumplir un método recursivo: Asegurar que existe una condición de salida, en la que no se producen llamadas recursivas (caso base) Asegurar que se cubren todos los posibles casos entre el base ylos no base Cada llamada, en el caso no base, conduce a problemas cada vez más pequeños que terminarán en el caso base

2

Agenda
Introducción Ejemplos Factorial Invertir un Número ResolverLaberinto Cuándo utilizar Recursividad Algoritmos de Backtracking Las Ocho Reinas Sudoku Resumen

Ejemplo: Factorial
Definición del factorial (definición recursiva): n! = n * (n-1)! , para n > 1 1! = 1Casos y Soluciones:
Casos
n = 1 (caso base) n>1

Soluciones
return 1 return n * factorial(n – 1)

3

Ejemplo: Factorial

Agenda
Introducción Ejemplos Factorial Invertir un Número ResolverLaberinto Cuándo utilizar Recursividad Algoritmos de Backtracking Las Ocho Reinas Sudoku Resumen

4

Ejemplo: Invertir un Número

Agenda
Introducción Ejemplos Factorial Invertir un NúmeroResolver Laberinto Cuándo utilizar Recursividad Algoritmos de Backtracking Las Ocho Reinas Sudoku Resumen

5

Ejemplo: Resolver Laberinto

Ejemplo: Resolver Laberinto

6

Agenda
IntroducciónEjemplos Factorial Invertir un Número Resolver Laberinto Cuándo utilizar Recursividad Algoritmos de Backtracking Las Ocho Reinas Sudoku Resumen

Cuándo utilizar recursividad
En general, las...