Entender la recursión

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Definición

  • Una función que se llama a sí misma
  • Casi todas las situaciones donde usamos bucles
    • se pueden sustituir por recursión
  • Puede resolver problemas que parecen muy complejos al principio
Estructuras de datos y algoritmos en Python

Ejemplo: factorial

$n!$

Estructuras de datos y algoritmos en Python

Ejemplo: factorial

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120
Estructuras de datos y algoritmos en Python

Ejemplo: factorial con recursión

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)
  • ¡Se ejecuta para siempre!
Estructuras de datos y algoritmos en Python

Ejemplo: identificar el caso base

  • Añade una condición
    • evita que el algoritmo se ejecute para siempre
  • Caso base del factorial -> $n=1$
def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120
Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • El ordenador usa una pila para llevar el control de las funciones
    • Pila de llamadas
Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • Empieza factorial(5)
  • Antes de que termine factorial(5) -> empieza factorial(4)
  • Antes de que termine factorial(4) -> empieza factorial(3)

Imagen de una cola con un elemento que representa una función.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • Empieza factorial(5)
  • Antes de que termine factorial(5) -> empieza factorial(4)
  • Antes de que termine factorial(4) -> empieza factorial(3)
  • Antes de que termine factorial(3) -> empieza factorial(2)

Imagen de una cola con dos elementos que representan dos funciones.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • Empieza factorial(5)
  • Antes de que termine factorial(5) -> empieza factorial(4)
  • Antes de que termine factorial(4) -> empieza factorial(3)
  • Antes de que termine factorial(3) -> empieza factorial(2)
  • Antes de que termine factorial(2) -> empieza factorial(1)

Imagen de una cola con tres elementos que representan tres funciones.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • Empieza factorial(5)
  • Antes de que termine factorial(5) -> empieza factorial(4)
  • Antes de que termine factorial(4) -> empieza factorial(3)
  • Antes de que termine factorial(3) -> empieza factorial(2)
  • Antes de que termine factorial(2) -> empieza factorial(1)

Imagen de una cola con cuatro elementos que representan cuatro funciones.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • factorial(1) termina
    • devuelve 1
  • factorial(2) termina

Imagen de una cola con cuatro elementos que representan cuatro funciones.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • factorial(1) termina
    • devuelve 1
  • factorial(2) termina
    • devuelve 2

Imagen de una cola con cuatro elementos que representan cuatro funciones. La última función va acompañada de su valor de retorno.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • factorial(1) termina
    • devuelve 1
  • factorial(2) termina
    • devuelve 2
  • factorial(3) termina
    • devuelve 6

Imagen de una cola con tres elementos que representan tres funciones.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • factorial(1) termina
    • devuelve 1
  • factorial(2) termina
    • devuelve 2
  • factorial(3) termina
    • devuelve 6
  • factorial(4) termina
    • devuelve 24

Imagen de una cola con dos elementos que representan dos funciones.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • factorial(1) termina
    • devuelve 1
  • factorial(2) termina
    • devuelve 2
  • factorial(3) termina
    • devuelve 6
  • factorial(4) termina
    • devuelve 24
  • factorial(5) termina
    • devuelve 120

Imagen de una cola con un elemento que representa una función.

Estructuras de datos y algoritmos en Python

Cómo funciona la recursión

  • factorial(1) termina
    • devuelve 1
  • factorial(2) termina
    • devuelve 2
  • factorial(3) termina
    • devuelve 6
  • factorial(4) termina
    • devuelve 24
  • factorial(5) termina
    • devuelve 120

Imagen de una cola vacía.

Estructuras de datos y algoritmos en Python

Programación dinámica

  • Técnica de optimización
  • Se aplica sobre todo a la recursión
  • Puede reducir la complejidad de algoritmos recursivos
  • Útil para:
    • Problemas que se dividen en subproblemas más pequeños
    • Subproblemas que se solapan
  • Guarda soluciones de subproblemas para no recalcular
    • Memoización
Estructuras de datos y algoritmos en Python

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python

Preparing Video For Download...