Conteúdo principal
Curso: Computer science theory > Unidade 1
Lição 6: Algoritmos recursivos- Recursividade
- A função fatorial
- Desafio: Fatorial iterativo
- Fatorial recursivo
- Desafio: Fatorial recursivo
- Propriedades de algoritmos recursivos
- Usando recursividade para determinar se uma palavra é um palíndromo
- Desafio: A string é um palíndromo?
- Calculando a potência de um número
- Desafio: Potência recursiva
- Recursão múltipla com o triângulo de Sierpinski
- Melhorando a eficiência das funções recursivas
- Projeto: Arte recursiva
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
A função fatorial
For our first example of recursion, let's look at how to compute the factorial function. We indicate the factorial of by . It's just the product of the integers 1 through . Por exemplo, 5! equals , or 120. (Note: Wherever we're talking about the factorial function, all exclamation points refer to the factorial function and are not for emphasis.)
Você pode estar se perguntando por que nós nos importaríamos com a função fatorial. Ela é muito útil quando estamos tentando contar quantas diferentes ordenações existem ou em quantas formas diferentes podemos combinar coisas. Por exemplo, de quantas maneiras diferentes podemos arranjar coisas? Nós temos escolhas para a primeira coisa. Para cada uma dessas escolhas, ficamos com escolhas para a segunda coisa, de modo que temos escolhas para as duas primeiras coisas, nessa ordem. Agora, para cada uma dessas duas primeiras escolhas, ficamos com escolhas para a terceira coisa, resultando em escolhas para as três primeiras coisas, em sequência. E assim por diante, até chegarmos a apenas duas coisas restantes, e finalmente só uma coisa restando. Então temos modos que podemos ordenar coisas. E este produto é exatamente ( fatorial), mas com a multiplicação escrita a partir de até 1 em vez de 1 até .
Outro uso para a função fatorial é para contar de quantos modos você pode selecionar coisas de uma coleção de objetos. Por exemplo, suponha que você está indo viajar e quer escolher quais camisetas levar. Digamos que você tenha camisetas, mas você tem espaço para colocar na mala apenas delas. De quantas formas diferentes você pode selecionar camisetas da coleção de camisetas? A resposta (que não demonstraremos matematicamente aqui) é . Portanto, a função fatorial pode ser bastante útil. Você pode aprender mais sobre permutações e combinações aqui, mas você não precisa compreendê-las para implementar um algoritmo fatorial.
The factorial function is defined for all positive integers, along with 0. Qual deve ser o valor de 0! ? It's the product of all integers greater than or equal to 1 and less than or equal to 0. But there are no such integers. Portanto, definimos 0! to equal the identity for multiplication, which is 1. (Definir 0! = 1 meshes nicely with the formula for choosing things out of things. Suppose that we want to know how many ways there are to choose things out of things. That's easy, because there is only one way: choose all things. So now we know that, using our formula, should equal 1. But is 0!, so now we know that should equal 1. If we cancel out the in both the numerator and denominator, we see that should equal 1, and it does because 0! é igual a 1).
Então agora temos um modo de pensar em . It equals 1 when , and it equals when is positive.
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?
- Esse artigo está sem tradução !(8 votos)
- No Google Chrome tem o tradutor automático .(0 votos)