If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

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, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. Mas perceba que left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 é mais uma maneira de dizer left parenthesis, n, minus, 1, right parenthesis, ! e, portanto, podemos dizer que n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. Você viu o que fizemos? Escrevemos n, ! como um produto no qual um dos fatores é left parenthesis, n, minus, 1, right parenthesis, !. Nós dizemos que podemos calcular n, ! ao calcular left parenthesis, n, minus, 1, right parenthesis, ! e multiplicar o resultado por n. Você pode calcular a função fatorial em n ao, primeiramente, calcular a função fatorial de n, minus, 1. Podemos dizer que calcular left parenthesis, n, minus, 1, right parenthesis, ! é um subproblema que resolvemos para calcular n!.
Vamos ver um exemplo: o cálculo de 5!.
  • Você pode calcular 5! como 5, dot, 4, !.
  • Agora você precisa solucionar o subproblema de calcular 4!, que você pode calcular como 4, dot, 3!.
  • Agora você precisa solucionar o subproblema de calcular 3!, que é 3, dot, 2, !.
  • Agora 2!, que é 2, dot, 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, !, equals, 1, dot, 0, !. Vamos fazer aplicando a fórmula.
  • Definimos que 0! é igual a 1.
  • Agora você pode calcular que 1, !, equals, 1, dot, 0, !, equals, 1.
  • Tendo calculado 1, !, equals, 1, você pode calcular 2, !, equals, 2, dot, 1, !, equals, 2.
  • Tendo calculado 2, !, equals, 2, você pode calcular 3, !, equals, 3, dot, 2, !, equals, 6.
  • Tendo calculado 3, !, equals, 6, você pode calcular 4, !, equals, 4, dot, 3, !, equals, 24.
  • Finalmente, tendo calculado 4, !, equals, 24, você pode terminar calculando 5, !, equals, 5, dot, 4, !, equals, 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, equals, 0, declare que n, !, equals, 1.
  • Caso contrário, n precisa ser positivo. Solucione o subproblema de calcular left parenthesis, n, minus, 1, right parenthesis, !, 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.