Para valores positivos de n n , vamos escrever n! n! como fizemos anteriormente, como um produto de números iniciados a partir de n n indo até 1: n! n! = n(n1)21 n \cdot (n-1) \cdots 2 \cdot 1 . Mas perceba que (n1)21 (n-1) \cdots 2 \cdot 1 é mais uma maneira de dizer (n1)! (n-1)! e, portanto, podemos dizer que n!=n(n1)! n! = n \cdot (n-1)! . Você viu o que fizemos? Escrevemos n! n! como um produto no qual um dos fatores é (n1)! (n-1)! . Nós dizemos que podemos calcular n! n! ao calcular (n1)! (n-1)! e multiplicar o resultado por n n . Você pode calcular a função fatorial em n n ao, primeiramente, calcular a função fatorial de n1 n-1 . Podemos dizer que calcular (n1)! (n-1)! é um subproblema que resolvemos para calcular n n !.
Vamos ver um exemplo: o cálculo de 5!.
  • Você pode calcular 5! como 54! 5 \cdot 4! .
  • Agora você precisa solucionar o subproblema de calcular 4!, que você pode calcular como 43 4 \cdot 3 !.
  • Agora você precisa solucionar o subproblema de calcular 3!, que é 32! 3 \cdot 2! .
  • Agora 2!, que é 21! 2 \cdot 1! .
  • 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! 1! = 1 \cdot 0! . Vamos fazer aplicando a fórmula.
  • Definimos que 0! é igual a 1.
  • Agora você pode calcular que 1!=10!=1 1! = 1 \cdot 0! = 1 .
  • Tendo calculado 1!=1 1! = 1 , você pode calcular 2!=21!=2 2! = 2 \cdot 1! = 2 .
  • Tendo calculado 2!=2 2! = 2 , você pode calcular 3!=32!=6 3! = 3 \cdot 2! = 6 .
  • Tendo calculado 3!=6 3! = 6 , você pode calcular 4!=43!=24 4! = 4 \cdot 3! = 24 .
  • Finalmente, tendo calculado 4!=24 4! = 24 , você pode terminar calculando 5!=54!=120 5! = 5 \cdot 4! = 120 .
Então, agora temos outro modo de pensar em como calcular o valor de n! n! para todos os n n números inteiros não-negativos:
  • Se n=0 n = 0 , declare que n!=1 n! = 1 .
  • Caso contrário, n n precisa ser positivo. Solucione o subproblema de calcular (n1)! (n-1)! , multiplique o resultado por n n , e declare n! n! igual ao resultado desse produto.
Quando calculamos n! 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.
Carregando