Olá, Visitante!
Páginas: [1]   Ir para o Fundo

Autor Tópico: Algoritmos #3 - Recursividade  (Lida 1006 vezes)

0 Membros e 1 Visitante estão vendo este tópico.

  • *
  • Mensagens: 2395 Ouro: 1747

    Medalhas:
    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
Algoritmos #3 - Recursividade
« Online: 08 Abr 2014, 19:18 »
Índice das aulas básicas
Índice das aulas avançadas
Índice das aulas de algoritmos
Recursividade
Conhecimento necessário : médio
Introdução

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.

Fatorial


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!

Código: [Selecionar]
def fatorial(n)
  if n == 0
    return 1
  else
    return n * fatorial(n-1)
  end
end

ou mais resumidamente ainda,
Código: [Selecionar]
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.


Exponencial

Mais para dar como um exemplo, fazer a exponencial com recursividade.
Código: [Selecionar]
def exponencial(x, n)
  if n == 0
    return 1
  else
    return x * exponencial(x, n-1)
  end
end

Ou resumidamente
Código: [Selecionar]
def exponencial(x, n)
  n == 0 ? 1 : x * exponencial(x, n-1)
end

Fibonacci

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.
Código: [Selecionar]
def fibonacci(n)
  if n <= 1
    return 1
  else
    return fibonacci(n-1) + fibonacci(n-2)
  end
end

Ou resumidamente
Código: [Selecionar]
def fibonacci(n)
  n <= 1 ? 1 : fibonacci(n-1) + fibonacci(n-2)
end


Finalizando

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 :)
« Última modificação: 10 Abr 2014, 14:04 por Raizen »

  • *
  • Mensagens: 210 Ouro: 92
    • Facebook
    • Ver perfil
Re: Recursividade
« Resposta #1 Online: 08 Abr 2014, 19:47 »
Opa aula muito boa raizen. Eu sempre me enrolo para aplicar a recursividade nos meus códigos, nunca enxergo onde aplicá-lo .-.

  • *
  • Mensagens: 2395 Ouro: 1747

    Medalhas:
    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
Re:  Recursividade
« Resposta #2 Online: 10 Abr 2014, 23:31 »
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.

  • *
  • Elmo de Natal
  • Mensagens: 169 Ouro: 634

    Medalhas:
    Melhor pontuação no Evento X'mas Factory

  • "Can't find a door, make your own!"
    • DeviantArt
    • Ver perfil
Re: Algoritmos #3 - Recursividade
« Resposta #3 Online: 11 Abr 2014, 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º
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), e colocam no corpo das mensagens o que deveria ser a assinatura?

  • *
  • Mensagens: 591 Ouro: 1212
  • Maker Geral
    • Unity
    • MSN Messenger - michaelwilliansantos@hotmail.com
    • Facebook
    • DeviantArt
    • Ver perfil
    • E-mail
Re: Algoritmos #3 - Recursividade
« Resposta #4 Online: 11 Abr 2014, 16:23 »
 Ta aí algo bem importante na qual os scripters hoje precisam saber.... Um exemplo abaixo usando recursividade..

Código: [Selecionar]
# Sem
index ||= 0
max = 5
if Input.trigger?(:UP)
  unless index >= max
    index += 1
  else
    index = 0
  end
end

Código: [Selecionar]
# 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.
"Amamos aquilo que amamos. A razão não entra nisso. Sob muitos aspectos, o amor insensato é o mais verdadeiro. Qualquer um pode amar uma coisa por causa de. É tão fácil quanto por um vintém no bolso. Mas amar algo apesar de, conhecer suas falhas e amá-las também, isto é raro, puro e perfeito". (O Temor do Sábio, pág. 58)

  • *
  • Mensagens: 2395 Ouro: 1747

    Medalhas:
    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
Re:  Algoritmos #3 - Recursividade
« Resposta #5 Online: 14 Abr 2014, 18:43 »
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:

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

Código: [Selecionar]
# Sem
index ||= 0
max = 5
if Input.trigger?(:UP)
  unless index >= max
    index += 1
  else
    index = 0
  end
end

Código: [Selecionar]
# 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.

Páginas: [1]   Ir para o Topo
 

SMF 2.0.2 | SMF © 2013, Simple Machines | Mobile View
© Centro RPG Maker - Alguns direitos reservados.
Layout por Uhtred