Se você está vendo esta mensagem, significa que estamos tendo problemas para carregar recursos externos em nosso website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Conteúdo principal

Fatorial recursivo

Para valores positivos de n, vamos escrever n! como fizemos anteriormente, como um produto de números iniciados a partir de n indo até 1: n! = n(n1)21. Mas perceba que (n1)21 é mais uma maneira de dizer (n1)! e, portanto, podemos dizer que n!=n(n1)!. Você viu o que fizemos? Escrevemos n! como um produto no qual um dos fatores é (n1)!. Nós dizemos que podemos calcular n! ao calcular (n1)! e multiplicar o resultado por n. Você pode calcular a função fatorial em n ao, primeiramente, calcular a função fatorial de n1. Podemos dizer que calcular (n1)! é um subproblema que resolvemos para calcular n!.
Vamos ver um exemplo: o cálculo de 5!.
  • Você pode calcular 5! como 54!.
  • Agora você precisa solucionar o subproblema de calcular 4!, que você pode calcular como 43!.
  • Agora você precisa solucionar o subproblema de calcular 3!, que é 32!.
  • Agora 2!, que é 21!.
  • Agora você precisa calcular 1!. Podemos dizer que 1! é igual a 1, porque é o produto de todos os números inteiros de 1 até 1. Ou você pode aplicar a fórmula 1!=10!. Vamos fazer aplicando a fórmula.
  • Definimos que 0! é igual a 1.
  • Agora você pode calcular que 1!=10!=1.
  • Tendo calculado 1!=1, você pode calcular 2!=21!=2.
  • Tendo calculado 2!=2, você pode calcular 3!=32!=6.
  • Tendo calculado 3!=6, você pode calcular 4!=43!=24.
  • Finalmente, tendo calculado 4!=24, você pode terminar calculando 5!=54!=120.
Então, agora temos outro modo de pensar em como calcular o valor de n! para todos os n números inteiros não-negativos:
  • Se n=0, declare que n!=1.
  • Caso contrário, n precisa ser positivo. Solucione o subproblema de calcular (n1)!, multiplique o resultado por n, e declare n! igual ao resultado desse produto.
Quando calculamos n! dessa maneira, chamamos o primeiro caso, no qual sabemos imediatamente a resposta, o caso base, e chamamos o segundo caso, no qual temos que calcular a mesma função mas com um valor diferente, o caso recursivo.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.