Παράδειγμα 3.8.3, Κεφάλαιο 3, Βιβλίο Μαθητή, Υπολογισμός αριθμών ακολουθίας Fibonacci (εκτός ύλης)

Για καλύτερη κατανόηση της διαφοράς μεταξύ επαναληπτικών και αναδρομικών μεθόδων, στη συνέχεια θα εξετασθεί ένα τελευταίο παράδειγμα, όπου υπολογίζεται η ακολουθία αριθμών 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