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: