Algoritmos #3 - Recursividade

[Raizen]

[box class=windowbg1]

Índice das aulas básicas

• Aula 1 - Introdução
  
• Aula 2 - Objetos
  
• Aula 3 - Operações
  
• Aula 4 - Condições
  
• Aula 5 - Repetição
  
• Aula 6 - Arrays
  
• Aula 7 - Hashes
  [/box]
  [box class=windowbg1]
  Índice das aulas avançadas
• Aula 8 - Superclasses e instâncias
  [/box]
  [box class=windowbg1]
  Índice das aulas de algoritmos
• Aula 1 - Sort
  
• Aula 2 - Busca
  
• Aula 3 - Recursividade
  [/box]
  
  [box class=windowbg]
  Recursividade
  [/box]
  
  Conhecimento necessário : médio
  [box class=windowbg]
  Introdução
  [/box]
  [box class=windowbg2]
  Bom antes de tudo, isso não é uma aula para iniciantes na programação, é para quem já tem uma ideia de como funciona a programação e são aulas isoladas entre si para explicarem um pouco mais sobre a programação.
  
  A aula atual é a recursividade,
  Definição tirada do wikipédia "Recursividade é um termo usado de maneira mais geral para descrever o processo de repetição de um objeto de um jeito similar ao que já fora mostrado. Um bom exemplo disso são as imagens repetidas que aparecem quando dois espelhos são apontados um para o outro."
  
  Traduzindo para programação, seria a reutilização de um mesmo bloco inúmeras vezes.
  
  
  O programa, ele consegue guardar um número muito grande de informação antes de "liberar" essa informação, a recursividade utiliza dessa "brecha" para que um código com 2 linhas faça o mesmo que códigos mais extensos. A recursividade é usada para rapidamente ter uma função pronta, ela não é o modo mais eficiente, mas é o mais limpo.
  
  Tirado do arquivo do Ricardo Alves de Java
  
  A ideia é criar um método que chame ele mesmo até atingir a base, na base o valor é fixo e a partir dai subimos a fila fazendo o processo inverso para obter o resultado. Complicado? Parece, mas não é :D.
  
  Vou fazer o mesmo do exemplo acima que é o fatorial e ai poderão entender como funciona a recursividade.
  [/box]
  
  [box class=windowbg]
  Fatorial
  [/box]
  
  [box class=windowbg2]
  A ideia para o fatorial é simples, para quem não conhece isso daqui 5!, significa fatorial de 5, e o fatorial pega o número e multiplica pelo anterior até atingir o número 1.
  Resumindo
  5! = 5 * 4 * 3 * 2 * 1
  ou seja 5! = 120
  
  o 0! é igual a 1 por definição,
  Bom vamos usar recursividade para resolver o problema!
  
  

  def fatorial(n)
    if n == 0
      return 1
    else
      return n * fatorial(n-1)
    end
  end
  

  
  
  ou mais resumidamente ainda,
  

  def fatorial(n)
    n == 0 ? 1 : n * fatorial(n-1)
  end
  

  
  
  Basicamente, ele faz exatamente o que a imagem lá em cima demonstra, se colocarmos
  p fatorial(4)
  
  Ele vai inserir o 4 no método fatorial, como ele não é igual a 0 ele retorna 4 * fatorial(3), ai o fatorial de 3 faz a mesma coisa e assim até atingir a base, que seria o fatorial(0) que sabemos que retorna 1.
  E ai faz o processo inverso, multiplica o 1 por 1, depois por 2, depois por 3 e depois por 4 e assim retorna o valor total.
  
  [/box]
  
  [box class=windowbg]
  Exponencial
  [/box]
  [box class=windowbg2]
  Mais para dar como um exemplo, fazer a exponencial com recursividade.
  

  def exponencial(x, n)
    if n == 0 
      return 1 
    else
      return x * exponencial(x, n-1)
    end
  end
  

  
  
  Ou resumidamente
  

  def exponencial(x, n)
    n == 0 ? 1 : x * exponencial(x, n-1)
  end
  

  
  [/box]
  
  [box class=windowbg]
  Fibonacci
  [/box]
  [box class=windowbg2]
  Para finalizar vamos fazer uma função, no caso do Ruby, um método que retorne o valor usando a sequencia de fibonacci, ou seja,
  1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
  se eu chamar fibonacci(6), ele pegaria o sexto na sequencia, e retornaria 13., pois a contagem é feita a partir do 0 na função a seguir.
  

  def fibonacci(n)
    if n <= 1
      return 1
    else
      return fibonacci(n-1) + fibonacci(n-2)
    end
  end
  

  
  
  Ou resumidamente
  

  def fibonacci(n)
    n <= 1 ? 1 : fibonacci(n-1) + fibonacci(n-2)
  end
  

  
  
  [/box]
  
  [box class=windowbg]
  Finalizando
  [/box]
  [box class=windowbg2]
  A ideia da recursividade é usar uma pilha que já está inclusa no próprio programa a seu favor, ele cria um laço e utiliza uma memória do programa para guardar os valores e usa-los depois, apesar de não ser a pratica mais eficaz, ela é muito bem utilizada no momento que precisa de algo rápido e que faz o que é necessário.
  
  Bom espero que tenham gostado, e em breve mais aulas sobre as praticas de programação :)
  [/box]
  

[Klarth]

Opa aula muito boa raizen. Eu sempre me enrolo para aplicar a recursividade nos meus códigos, nunca enxergo onde aplicá-lo .-.

[Raizen]

Opa aula muito boa raizen. Eu sempre me enrolo para aplicar a recursividade nos meus códigos, nunca enxergo onde aplicá-lo .-.

Vlws manolo xD, aah é meio complicado k, ele serve bastante para funções tipo fatorial e talz, e outras coisas como ponteiros e panz, mas em geral é mais para saber que é possível ser feito xD.

[Pretty-Belle]

Otima aula xD (desculpa ai pela falta de acentos, meu teclado ta me trollando .-.) Lembro do costume que tinha de fazer uma em metodo 'interativo' (nao sei pq, mas meu prof chama assim xD) e quando eu aprendi recursao tudo clareou vei, lol. Pena que gaste tanta memoria. Mas no fim e muito mais facil e intuitivo xD
Aguardo a proximo aula ºuº

[Kvothe]

 Ta aí algo bem importante na qual os scripters hoje precisam saber.... Um exemplo abaixo usando recursividade..

# Sem
index ||= 0
max = 5
if Input.trigger?(:UP)
  unless index >= max
    index += 1 
  else
    index = 0
  end
end

# Com
index ||= 0
max = 5
index = index >= max ? 0 : index.next if Input.trigger?(:UP)

Alem de deixar o código bonito é muito mais prático.

[Raizen]

Otima aula xD (desculpa ai pela falta de acentos, meu teclado ta me trollando .-.) Lembro do costume que tinha de fazer uma em metodo 'interativo' (nao sei pq, mas meu prof chama assim xD) e quando eu aprendi recursao tudo clareou vei, lol. Pena que gaste tanta memoria. Mas no fim e muito mais facil e intuitivo xD
Aguardo a proximo aula ºuº

Vlws Pretty <3 , ah, é mais tipo para ter uma "arma" a mais para programar, mas realmente não é o melhor jeito, vlws ai e eu não sabia que estava fazendo curso relacionado a computação 

Ta aí algo bem importante na qual os scripters hoje precisam saber.... Um exemplo abaixo usando recursividade..

# Sem
index ||= 0
max = 5
if Input.trigger?(:UP)
  unless index >= max
    index += 1 
  else
    index = 0
  end
end

# Com
index ||= 0
max = 5
index = index >= max ? 0 : index.next if Input.trigger?(:UP)

Alem de deixar o código bonito é muito mais prático.

Ah sim quase isso, só que não sei se esse joga na "reserva" da memória para depois puxar xD.