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

Curso: Computer science theory > Unidade 1

Lição 6: Algoritmos recursivos
Computação
Computer science theory
Algoritmos
Algoritmos recursivos
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies

Fatorial recursivo

Google Sala de Aula
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⋅(n−1)⋯2⋅1. Mas perceba que (n−1)⋯2⋅1 é mais uma maneira de dizer (n−1)! e, portanto, podemos dizer que n!=n⋅(n−1)!. Você viu o que fizemos? Escrevemos n! como um produto no qual um dos fatores é (n−1)!. Nós dizemos que podemos calcular n! ao calcular (n−1)! e multiplicar o resultado por n. Você pode calcular a função fatorial em n ao, primeiramente, calcular a função fatorial de n−1. Podemos dizer que calcular (n−1)! é um subproblema que resolvemos para calcular n!.
Vamos ver um exemplo: o cálculo de 5!.
  • Você pode calcular 5! como 5⋅4!.
  • Agora você precisa solucionar o subproblema de calcular 4!, que você pode calcular como 4⋅3!.
  • Agora você precisa solucionar o subproblema de calcular 3!, que é 3⋅2!.
  • Agora 2!, que é 2⋅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!=1⋅0!. Vamos fazer aplicando a fórmula.
  • Definimos que 0! é igual a 1.
  • Agora você pode calcular que 1!=1⋅0!=1.
  • Tendo calculado 1!=1, você pode calcular 2!=2⋅1!=2.
  • Tendo calculado 2!=2, você pode calcular 3!=3⋅2!=6.
  • Tendo calculado 3!=6, você pode calcular 4!=4⋅3!=24.
  • Finalmente, tendo calculado 4!=24, você pode terminar calculando 5!=5⋅4!=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 (n−1)!, 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?

Entrar
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.