O TEMA DO FÓRUM ESTÁ EM MANUTENÇÃO. FEEDBACKS AQUI: ACESSAR

Algoritmos #3 - Recursividade

Iniciado por Raizen, 08/04/2014 às 19:18

08/04/2014 às 19:18 Última edição: 10/04/2014 às 14:04 por 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]

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

Citação de: Klarth online 08/04/2014 às 19:47
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.

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º
Já perceberam que em vez de as pessoas usarem esse espaço para uma assinatura de fato, elas colocam alguma coisa aleatória (imagem, frase filosófica, divulgação, tipo o que estou fazendo agora), e colocam no corpo das mensagens o que deveria ser a assinatura?

 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.



Citação de: Pretty-Belle online 11/04/2014 às 08:59
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  :o:

Citação de: Dax online 11/04/2014 às 16:23
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.