Funcția factorial

Pentru primul nostru exemplu de recursivitate, hai să ne uităm cum se calculează funcția factorial. Notăm factorialul lui $n$‍ cu $n!$‍. Reprezintă produsul numerelor întregi de la 1 până la $n$‍. De exemplu, 5! este egal cu $1\cdot 2\cdot 3\cdot 4\cdot 5$‍, adică 120. (Observație: Ori de câte ori vorbim despre funcția factorial, semnul exclamării se referă la factorial, nu la accentuare.)

Probabil te întrebi de ce ar trebui să ne pese de funcția factorial. Este foarte utilă dacă vrem să calculăm în câte moduri se pot aranja obiecte sau în câte moduri se pot combina. De exemplu, în câte moduri se pot aranja $n$‍ obiecte? Avem $n$‍ variante pentru primul obiect. Pentru fiecare dintre aceste $n$‍ variante, ne rămân $n-1$‍ variante pentru al doilea obiect, adică $n\cdot (n-1)$‍ variante de a aranja primele două obiecte. Apoi, pentru fiecare dintre acestea, avem $n-2$‍ variante pentru al treilea obiect; astfel că avem $n\cdot (n-1)\cdot (n-2)$‍ variante pentru primele trei obiecte, în ordine. Continuăm tot așa, până când ne mai rămân doar două obiecte, apoi doar unul singur. În total, avem $n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$‍ modalități de ordonare a $n$‍ obiecte. Ei bine, acest produs este tocmai $n!$‍ ($n$‍ factorial), numai că s-a scris produsul începând de la $n$‍ până la 1, în loc de a-l scrie de la 1 către $n$‍.

O altă utilitate a funcției factorial reprezintă posibilitatea de a calcula în câte moduri putem alege obiecte dintr-o colecție. De exemplu, să presupunem că mergi într-o excursie și vrei să alegi ce tricouri vei lua. Să zicem că tu ai $n$‍ tricouri, dar nu au loc în bagaj decât $k$‍. În câte moduri poți alege $k$‍ tricouri dintr- colecție de $n$‍ tricouri? Răspunsul (pe care nu îl vom demonstra aici) este tocmai $n!/(k!\cdot (n-k)!)$‍. Deci, funcția factorial este chiar foarte utilă. Poți învăța mai multe despre permutări și combinări aici, deși nu este absolut necesar să le înțelegi pentru a implementa un algoritm factorial.

Funcția factorial este definită pentru toate numerele pozitive, începând cu 0. Oare 0! ce valoare are putea să aibă? Este produsul tuturor numerelor mai mari sau egale cu 1 și mai mici sau egale cu 0. Dar nu există asemenea numere întregi. De aceea, îl definim pe 0! ca fiind egal cu elementul neutru față de înmulțire, adică 1. (Definind 0! = 1 se potrivește bine cu formula pentru alegerea a $k$‍ obiecte dintr-un total de $n$‍ obiecte. Să presupunem că vrem să vedem în câte moduri pot fi alese $n$‍ obiecte dintr-un total de $n$‍ obiecte. Așadar, folosind formula $n!/(n!\cdot (n-n)!)$‍ ar trebui să avem 1. Dar $(n-n)!$‍ este 0!, deci $n!/(n!\cdot 0!)$‍ar trebui să fie egal cu 1. Dacă simplificăm pe $n!$‍ de la numărător și numitor, vedem că $1/(0!)$‍ ar trebui să fie 1, ceea ce se întâmplă pentru că 0! este egal cu 1.)

Deci, acum avem o cale de a-l înțelege pe $n!$‍. Este egal cu 1 când $n=0$‍ și este egal cu $1\cdot 2\cdots (n-1)\cdot n$‍ când $n$‍ este pozitiv.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.