Функцията факториел

За нашия първи пример за рекурсия да видим как да изчислим функцията факториел. Записваме факториелът на $n$‍ като $n!$‍. Това е просто произведението на целите числа от 1 до $n$‍. Например 5! е равно на $1\cdot 2\cdot 3\cdot 4\cdot 5$‍, или 120. (Забележка: когато говорим за функцията факториел, всички удивителни се отнасят за тази функция, а не са акцент.)

Може би се чудиш защо се интересуваме от функцията факториел. Тя е много полезна, когато се опитваме да преброим колко различни подредби има за нещата или по колко различни начина можем да комбинираме някакви неща. Например по колко различни начина можем да подредим $n$‍ неща? За първото имаме $n$‍ избора. За всеки от тези $n$‍ избора ни остават по $n-1$‍ избора за второто нещо, така че имаме $n\cdot (n-1)$‍ избора за първите две неща в този ред. Сега, за всеки от тези два избора имаме $n-2$‍ избора за третото нещо, което ни дава $n\cdot (n-1)\cdot (n-2)$‍ избора за първите три неща в този ред. Продължаваме така, докато не стигнем до това да ни останат само две неща, а след това само едно нещо. Общо имаме $n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$‍ начина, по които можем да подредим $n$‍ неща. Това произведение е просто $n!$‍ ($n$‍ факториел), но с произведението, записано от $n$‍ д 1, а не от 1 до $n$‍.

Друга употреба на факториела е да преброим по колко начина можеш да избереш неща от колекция. Например да предположим, че ще пътуваш и искаш да решиш кои тениски да вземеш. Да речем, че имаш $n$‍ тениски, но имаш място в багажа си само за $k$‍ от тях. По колко различни начина можеш да избереш $k$‍ тениски от колекция от $n$‍ тениски? Отговорът (който тук няма да се опитваме да оправдаем) излиза $n!/(k!\cdot (n-k)!)$‍. Така че функцията факториел може да бъде много полезна. Можеш да научиш повече за пермутациите и комбинациите тук, но не е необходимо да ги разбираш, за да имплементираш алгоритъма за факториел.

Функцията факториел е дефинирана за всички положителни цели числа и 0. Каква стойност трябва да има 0! ? Това е произведението на всички цели числа, които са по-големи или равни на 1 и са по-малки или равни на 0. Но такива цели числа няма. Следователно дефинираме 0! като равно на тъждеството за умножение, което е 1. (Дефинирането на 0! = 1 се описва добре от формулата за избиране на $k$‍ неща от $n$‍ неща. Да предположим, че искаме да знаем по колко начина можем да изберем $n$‍ неща от $n$‍ неща. Това е лесно, защото има само един начин: избираме всичките $n$‍ неща. Сега знаем, че като използваме нашата формула $n!/(n!\cdot (n-n)!)$‍ трябва да е равно на 1. Но $(n-n)!$‍ е 0!, затова знаем, че $n!/(n!\cdot 0!)$‍ трябва да е равно на 1. Ако съкратим $n!$‍ от числителя и знаменателя, виждаме, че $1/(0!)$‍ трябва да е равно на 1 и това е така, защото 0! е равно на 1.)

Така че вече имаме начин, по който да мислим за $n!$‍. Това е равно на 1, когато $n=0$‍, и е равно на $1\cdot 2\cdots (n-1)\cdot n$‍, когато $n$‍ е положително.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.