Gostou do nosso conteúdo? Te ajudou?
Nos ajude também! Faça um PIX, de qualquer valor:
programacao.progressiva@gmail.com
Mostrando postagens com marcador Fibonacci. Mostrar todas as postagens
Mostrando postagens com marcador Fibonacci. Mostrar todas as postagens

Função Recursiva em JavaScript: Fatorial e Fibonacci

Neste tutorial de nossa apostila de JavaScript, vamos aprender o importante conceito de recursividade em JS. Vamos usar tais conhecimentos para calcular o fatorial de um número bem como gerar a sequência de Fibonacci.

Obter meu certificado!

Recursividade em JavaScript


Até o momento, em nossos estudos sobre Funções em JavaScript, declaramos, criamos e invocamos funções de modo que cada uma faça 'sua parte' apenas e pronto, ou que função invoque outra função para poder realizar sua missão.

Porém, não é a única maneira que temos de utilizar as funções.

Chamamos de recursividade a capacidade de uma rotina invocar ela mesmo.
Em outras palavras: uma função recursiva é aquela que invoca ela mesma.

Sim, sei que pode parecer algo muito bizarro e abstrato, vamos mostrar na prática como isso funciona e você vai entender melhor a recursão.

Aliás, se fizer um código básico de uma função chamando outra função, apenas isso, você vai acabar tendo criado um vírus. Upe seu código para seu servidor web, e trolle seus amigos fazendo a memória RAM deles ser entupida de função chamando função e ele tendo que reiniciar o computador.

Função recursiva: Somatório

Vamos criar uma função que calcula o somatório de qualquer número n.
Dizemos que o somatório de n é S(n) e se calcula assim: 1 + 2 + 3 + ... + (n-1) + n

Por exemplo:
S(5) = 5 + 4 + 3 + 2 + 1
S(6) = 6 + 5 + 4 + 3 + 2 + 1
...

Mas note uma coisa interessante aí:
S(6) = 6 + S(5)
S(5) = 5 + S(4)
...

Generalizando:
S(n) = n + S(n-1)

Veja como ficou nosso código do somatório:


HTML:
<!DOCTYPE html>
<html>
 <head>
    <title>Apostila JavaScript Progressivo</title>
    <script type="text/javascript" src="script.js"></script>
 </head>
 <body>
  Numero:<input id="num" type="number">
  <button onclick="main()">Somatório</button><br />
  Resposta: <div id="resposta" style='display:inline'></div><br />
</html>
script.js:
function main()
{
 var num = parseInt(document.getElementById("num").value);
 var resp = document.getElementById("resposta");

 resp.innerHTML = somatorio(num);
}
function somatorio(x)
{
 if(x<=1)
  return 1;
 else
  return x + somatorio(x-1) ;
}
Resultado:
Numero:
Resposta:



Note uma coisa importante em funções recursivas: elas tem que ter um ponto de parada.
No caso do somatório, é: x<=1

Ou seja, ela vai ficar chamando ela mesma, e de novo, e de novo, e de novo...se você não der um stop nisso, vai ficar se invocando infinitamente.

No caso, quando atinge: S(1), ela retorna 1 e vai parar de se invocar!

Recursividade: Fatorial

Seja F(n) o fatorial de um inteiro positivo n, que é calculado por:
F(n) = n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1

Veja que:
F(n) = n * F(n-1)

Ou seja, podemos usar a recursividade para calcular o fatorial de um número!
Código HTML:


<!DOCTYPE html>
<html>
 <head>
    <title>Apostila JavaScript Progressivo</title>
    <script type="text/javascript" src="script.js"></script>
 </head>
 <body>
  Numero:<input id="num" type="number">
  <button onclick="main()">Fatorial</button><br />
  Resposta: <div id="resposta" style='display:inline'></div><br />
</html>
Código JavaScript:
function main()
{
 var num = parseInt(document.getElementById("num").value);
 var resp = document.getElementById("resposta");

 resp.innerHTML = fatorial(num);
}
function fatorial(x)
{
 if(x<=1)
  return 1;
 else
  return x * fatorial(x-1);
}
Resultado:
Numero:
Resposta:



Função Recursiva: Fibonacci


Seja n o enésimo termo da sequência de Fibonacci, ele é calculado como:
F(n) = F(n-1) + F(n-2)

Ou seja, cada elemento da sequência é a soma dos dois anteriores, onde:
F(1) = 0
F(2) = 1

Código HTML:
<!DOCTYPE html>
<html>
 <head>
    <title>Apostila JavaScript Progressivo</title>
    <script type="text/javascript" src="script.js"></script>
 </head>
 <body>
  Numero:<input id="num" type="number">
  <button onclick="main()">Fibonacci</button><br />
  Resposta: <div id="resposta" style='display:inline'></div><br />
</html>
script.js:
function main()
{
 var num = parseInt(document.getElementById("num").value);
 var resp = document.getElementById("resposta");

 resp.innerHTML = fibonacci(num);
}
function fibonacci(x)
{
 if(x<=2)
  return (x-1);
 else
  return ( fibonacci(x-1) + fibonacci(x-2) );
}
Resultado:
Numero:
Resposta:


3 comentários:
Marcadores: , , , , ,

Sequência de Fibonacci em JavaScript

Neste tutorial de JS, vamos aprender como gerar a sequência, e qualquer termo, da série de Fibonacci, usando laços FOR e WHILE em JavaScript.

A Sequência de Fibonacci


Assim como a PA (Progressão Aritmética), é uma sequência de números, formada por uma regras bem simples.

O primeiro número da série é 0.
O segundo é 1.

A partir daí, o próximo termo é sempre a soma dos dois anteriores. Logo:
Terceiro termo = 0 + 1 = 1
Quarto termo   = 1 + 1 = 2
Quinto termo   = 1 + 2 = 3
Sexto termo     = 2 + 3 = 5
Sétimo termo   = 3 + 5 = 8
Oitavo termo   = 5 + 8 = 13
...

Ela é de extrema importância na Matemática e aparece de maneira assustadora na Natureza, vale a pena uma pesquisa!

Série de Fibonacci em JavaScript

Crie um script que pede ao usuário um termo qualquer da série de Fibonacci e ele exiba tal termo.

O termo que o usuário quer ver será armazenado na variável termo, o número da sequência em numero. Além disso, temos que ter duas outras variáveis, que vão armazenar os dois últimos números da sequência: a ultimo e a penultimo.

Primeiro, precisamos tratar o caso que a pessoa digite termo 1 ou 2.
Nesse caso, basta fazer termo-1 .
Se ela tiver digitado 1, retorna 0. Se tiver digitado 2, retorna o valor 1.

Acima do termo 2, vamos entrar no laço for.
O próximo termo da sequência é:
numero = ultimo + penultimo

Agora, precisamos atualizar os valores de ultimo e penultimo:
penultimo = ultimo;
ultimo = numero


Veja como ficou:
Código HTML:
<!DOCTYPE html>
<html>
 <head>
   <title>Apostila JavaScript Progressivo</title>
   <script type="text/javascript" src="script.js"></script>
 </head>
 <body>
   Exibir até o termo: <input id="numero" type="number"> <br />
   <button onclick="fibonacci()">Exibir</button><br />
   <div id='resposta'></div>
 </body>
</html>
Código JavaScript:
function fibonacci(){
  var termo = parseInt(document.getElementById('numero').value);
  var resposta = document.getElementById('resposta');
  var penultimo=0, ultimo=1;
  var numero;

  if(termo<=2)
   numero = termo-1;
  else
   for(var count=3 ; count<=termo ; count++){
    numero = ultimo + penultimo;
    penultimo = ultimo;
    ultimo = numero;
   }

  resposta.innerHTML=numero;
}
Resultado:

Exibir o termo:



Fibonacci com laço WHILE

function fibonacci(){
  var termo = parseInt(document.getElementById('numero').value);
  var resposta = document.getElementById('resposta');
  var penultimo=0, ultimo=1;
  var numero;

  if(termo<=2)
   numero = termo-1;
  else{
   count=3;
   while(count<=termo){
    numero= ultimo + penultimo;
    penultimo = ultimo;
    ultimo=numero;
    count++;
   }
  }

  resposta.innerHTML=numero;
}


Exercício de JavaScript

Agora, em vez de exibir o termo, faça um script que printe na página todos os números da sequência de Fibonacci, até o termo escolhido pelo usuário.

Código: na apostila!
Resultado:
Exibir até o termo:


4 comentários:
Marcadores: , , , , , , , , , ,
Assinar: Postagens (Atom)