Για καλύτερη κατανόηση της διαφοράς μεταξύ επαναληπτικών και αναδρομικών μεθόδων, στη συνέχεια θα εξετασθεί ένα τελευταίο παράδειγμα, όπου υπολογίζεται η ακολουθία αριθμών Fibonacci πρώτης τάξης, που ορίζεται ως εξής:
ενώ οι πρώτοι όροι της ακολουθίας Fibonacci πρώτης τάξης είναι: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 κ.λπ.
ΛΥΣΗ:
Από τον ορισμό φαίνεται ανάγλυφα η αναδρομική φύση της συνάρτησης. Οι δύο επόμενοι αλγόριθμοι υπολογίζουν τον αριθμό Fibonacci πρώτης τάξης Fn με επαναληπτική και αναδρομική μέθοδο. Υποτίθεται ότι κατά την κλήση του αλγορίθμου μία μη αρνητική τιμή περνά ως όρισμα στη μεταβλητή n.
Αλγόριθμος Fibonacci1 Δεδομένα // n // Αν n ≤ 1 τότε Fib ← n f0 ← 0 f1 ← 1 Για i από 2 μέχρι n fib ← f0+f1 f0 ← f1 f1 ← fib Τέλος_επανάληψης Αποτελέσματα // Fib // Τέλος Fibonacci1 Αλγόριθμος Fibonacci2 Δεδομένα // n // Αν n ≤ 1 τότε Fib ← n αλλιώς Fib ← Fibonacci2(n-1) + Fibonacci2(n-2) Τέλος_Αν Αποτελέσματα // Fib // Τέλος Fibonacci2
Πρόσφατα σχόλια