Entendendo recursão

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Definição

• Função chamando a si mesma
• Quase todos os casos em que usamos loops
  • dá para substituir por recursão
• Resolve problemas que parecem bem complexos no início

Exemplo - fatorial

$n!$

Exemplo - fatorial

$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

Exemplo - fatorial com recursão

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

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

• Executa para sempre!

Exemplo - identificando o caso base

• Adicione uma condição
  • garante que o algoritmo não rode para sempre
• Caso base do fatorial -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

Como a recursão funciona

• O computador usa uma pilha para rastrear as funções
  • Call stack

Como a recursão funciona

• factorial(5) inicia
• Antes de factorial(5) terminar -> factorial(4) inicia
• Antes de factorial(4) terminar -> factorial(3) inicia

Como a recursão funciona

• factorial(5) inicia
• Antes de factorial(5) terminar -> factorial(4) inicia
• Antes de factorial(4) terminar -> factorial(3) inicia
• Antes de factorial(3) terminar -> factorial(2) inicia

Como a recursão funciona

• factorial(5) inicia
• Antes de factorial(5) terminar -> factorial(4) inicia
• Antes de factorial(4) terminar -> factorial(3) inicia
• Antes de factorial(3) terminar -> factorial(2) inicia
• Antes de factorial(2) terminar -> factorial(1) inicia

Como a recursão funciona

• factorial(5) inicia
• Antes de factorial(5) terminar -> factorial(4) inicia
• Antes de factorial(4) terminar -> factorial(3) inicia
• Antes de factorial(3) terminar -> factorial(2) inicia
• Antes de factorial(2) terminar -> factorial(1) inicia

Como a recursão funciona

• factorial(1) termina
  • retorna 1
• factorial(2) termina

Como a recursão funciona

• factorial(1) termina
  • retorna 1
• factorial(2) termina
  • retorna 2

Como a recursão funciona

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

Como a recursão funciona

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

Como a recursão funciona

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

Como a recursão funciona

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

Programação dinâmica

• Técnica de otimização
• Principalmente aplicada à recursão
• Pode reduzir a complexidade de algoritmos recursivos
• Usada para:
  • Problemas que podem ser divididos em subproblemas menores
  • Subproblemas se sobrepõem
• Soluções dos subproblemas são salvas para evitar recálculo
  • Memoization

Vamos praticar!

Estruturas de Dados e Algoritmos em Python