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 $n$‍ by $n!$‍. It's just the product of the integers 1 through $n$‍. Por exemplo, 5! equals $1\cdot 2\cdot 3\cdot 4\cdot 5$‍, 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 $n$‍ coisas? Nós temos $n$‍ escolhas para a primeira coisa. Para cada uma dessas $n$‍ escolhas, ficamos com $n-1$‍ escolhas para a segunda coisa, de modo que temos $n\cdot (n-1)$‍ escolhas para as duas primeiras coisas, nessa ordem. Agora, para cada uma dessas duas primeiras escolhas, ficamos com $n-2$‍ escolhas para a terceira coisa, resultando em $n\cdot (n-1)\cdot (n-2)$‍ 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 $n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$‍ modos que podemos ordenar $n$‍ coisas. E este produto é exatamente $n!$‍ ($n$‍ fatorial), mas com a multiplicação escrita a partir de $n$‍ até 1 em vez de 1 até $n$‍.

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 $n$‍ camisetas, mas você tem espaço para colocar na mala apenas $k$‍ delas. De quantas formas diferentes você pode selecionar $k$‍ camisetas da coleção de $n$‍ camisetas? A resposta (que não demonstraremos matematicamente aqui) é $n!/(k!\cdot (n-k)!)$‍. 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 $k$‍ things out of $n$‍ things. Suppose that we want to know how many ways there are to choose $n$‍ things out of $n$‍ things. That's easy, because there is only one way: choose all $n$‍ things. So now we know that, using our formula, $n!/(n!\cdot (n-n)!)$‍ should equal 1. But $(n-n)!$‍ is 0!, so now we know that $n!/(n!\cdot 0!)$‍ should equal 1. If we cancel out the $n!$‍ in both the numerator and denominator, we see that $1/(0!)$‍ should equal 1, and it does because 0! é igual a 1).

Então agora temos um modo de pensar em $n!$‍. It equals 1 when $n=0$‍, and it equals $1\cdot 2\cdots (n-1)\cdot n$‍ when $n$‍ 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.