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:

---

• Fatorial com laços WHILE e FOR

Função Recursiva: Fibonacci

Leia: Sequência de 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:

---

Fatorial com laços WHILE e FOR em JavaScript

Neste tutorial de JS, vamos te ensinar a calcular o fatorial de qualquer número, usando apenas o laço FOR ou o laço WHILE, em JavaScript.

• Apostila de JavaScript para download

Obter meu certificado!

Fatorial na Matemática

Em Matemática, dizemos que um número natural N é fatorial quando ele é representado por N! e vale:
N! = N * (N-1) * (N-2) * ... * 3 * 2 * 1

Ou seja, para saber quanto vale x! basta multiplicar x por x-1, depois por x-2, depois por x-3...até chegar na multiplicação por 2 e por 1.

Por exemplo:
5! = 5 x 4 x 3 x 2 x 1 = 120
6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040

Calcular Fatorial usando Laço FOR

Inicialmente, pedimos ao usuário um número inteiro positivo, maior ou igual a 1 e armazenamos na variável numero.

Depois, inicializamos uma variável resultado com o número 1.
Agora, basta multiplicar resultado por 1, depois por 2, depois por 3...depois por (numero-1) até multiplicar por numero.

Veja como fica.




Código HTML:

<!DOCTYPE html>
<html>
 <head>
   <title>Apostila JavaScript Progressivo</title>
   <script type="text/javascript" src="script.js"></script>
 </head>
 <body>
   Fatorial de: <input id="numero" type="number"> <br />
   <button onclick="fatorial()">Exibir</button><br />
   Resposta: <div id='resposta'></div>
 </body>
</html>

Código script.js:

function fatorial(){
  var numero = parseInt(document.getElementById('numero').value);
  var resposta = document.getElementById('resposta');
  var resultado=1;

  for(var count=1 ; count<=numero ; count++)
   resultado *= count;

  resposta.innerHTML =resultado;
}

Teste:

---

Fatorial de:

Resposta:

---

Fatorial com Laço WHILE

Veja se consegue entender o código do cálculo de um número fatorial usando o laço WHILE.
É basicamente a mesma coisa do FOR, mas temos que criar e inicializar a variável antes do laço e dentro dele temos que fazer o incremento.

script.js:

function fatorial(){
  var numero = parseInt(document.getElementById('numero').value);
  var resposta = document.getElementById('resposta');
  var resultado=1;
  var count=1;

  while(count<=numero){
   resultado *= count;
   count++;
  }

  resposta.innerHTML =resultado;
}

Resultado:

---

Fatorial de:

Resposta:

---