Recursive Algorithms


Factorial

Στα μαθηματικά, το παραγοντικό είναι ένας μη αρνητικός ακέραιος αριθμός N, που συμβολίζεται N! και ισούται με το γινόμενο όλων των θετικών ακεραίων που είναι μικρότεροι ή ίσοι του N. Για παράδειγμα, . Το 0! ισούται με 1 σύμφωνα με τη σύμβαση του κενού γινομένου. Το παραγοντικό χρησιμοποιείται σε αρκετούς τομείς των μαθηματικών όπως πιθανότητες, στατιστική, άλγεβρα και μαθηματική ανάλυση. Εμφανίζεται συνήθως όταν θέλουμε να διατάξουμε N διακριτά αντικείμενα σε μία ακολουθία (μεταθέσεις στο σύνολο των αντικειμένων) διότι αυτό επιτυγχάνεται με N! διαφορετικούς τρόπους.

Pseudocode

1.Factorial(n)
2.
if (n ≤ 1)

3.
return 1

4.
else

5.
temp ← n * Factorial(n - 1)

6.
return temp

7.
end if

8.end

Applet

Java applet that demonstrates factorial algorithm.

Example

Έστω ότι θέλουμε να υπολογίσουμε το 5! άρα n=5. Δεν ικανοποιείται η συνθήκη ελέγχου if οπότε θα εκτελεστεί η εντολή 5 * Factorial(4). Κατά την 2η κλήση του αλγορίθμου επίσης δεν ικανοποιείται η συνθήκη οπότε καλείται και πάλι ο αλγόριθμος. Αυτό συμβαίνει μέχρι το όρισμα της συνάρτησης Factorial να ισούται με 1, όπου και θα λάβει αποτέλεσμα 1. Τότε θα επιστρέψει στην προηγούμενη κλήση και θα πολλαπλασιαστεί με 2. Το ίδιο θα συνεχίσει να συμβαίνει μέχρι να επιστρέψει στην 1η κλήση του αλγορίθμου όπου το επιμέρους αποτέλεσμα θα πολλαπλασιαστεί με 5.

Factorial(5)=5*Factorial(4)=?
Factorial(4)=4*Factorial(3)=?
Factorial(3)=3*Factorial(2)=?
Factorial(2)=2*Factorial(1)=2*1=2
Factorial(3)=3*Factorial(2)=3*2=6
Factorial(4)=4*Factorial(3)=4*6=24
Factorial(5)=5*Factorial(4)=5*24=120
Το αποτέλεσμα είναι 120.