Ο Scott Hanselman έχει ένα πολύ ενδιαφέρον blog, στο οποίο κάθε τόσο ποστάρει διάφορα ενδιαφέροντα δείγματα κώδικα. Σε ένα από αυτά, ονόματι The Weekly Source Code 13 – Fibonacci Edition , έχει ποστάρει διάφορα τμήματα κώδικα για υπολογισμό του ν-οστού αριθμού Fibonacci (για όσους δεν θυμούνται, η ακολουθία Fibonacci είναι της μορφής an = an-1 + an-2)

Αρχικά, με C# 2.0 μπορούμε να κάνουμε το εξής

static int Fibonacci(int x)

{

if (x <= 1)

return x;

return Fibonacci(x – 1) + Fibonacci(x – 2);

}

Το οποίο, μπορεί να γραφτεί με το πολύ πιο όμορφο

static int Fibonacci(int x)

{

return x <= 1 ? x : Fibonacci(x – 1) + Fibonacci(x – 2);

}

 

Ιδιαίτερο ενδιαφέρον, παρουσιάζει ο υπολογισμός του με C# 3.0, ο οποίος γίνεται με το παρακάτω τμήμα κώδικα

Func<int, int> fib = null;

fib = n => n > 1 ? fib(n – 1) + fib(n – 2) : n;

Ίσως να αναρωτηθείτε, γιατί η δήλωση αρχικά ως null;; Δοκιμάστε να κάνετε compile το εξής:

Func<int, int> fib = n => n > 1 ? fib(n – 1) + fib(n – 2) : n;

Ο compiler διαμαρτύρεται ότι Error 1 Use of unassigned local variable ‘fib’ (δείτε ένα πολύ καλό blog post σχετικά με αυτό εδώ)

Ο compiler μας υποχρεώνει να έχουμε κάνει assign το fib, πριν μπορέσουμε να το χρησιμοποιήσουμε. Οπότε, ο “dirty” way για να το κάνουμε αυτό είναι να το δηλώσουμε ως null, οπότε και βγαίνει το παρακάτω, όπως πολύ σωστά έχει γράψει ο Scott

Func<int, int> fib = null;

fib = n => n > 1 ? fib(n – 1) + fib(n – 2) : n;

Με ένα

Console.WriteLine(fib(15));

βλέπουμε ότι το αποτέλεσμα είναι 610, οπότε ο υπολογισμός μας είναι σωστός.

Μπορεί να αναρωτηθείτε αν ο υπολογισμός όντως γίνεται αναδρομικά. Ισχύει, απλά δεν γίνεται ακριβώς αναδρομική κλήση συνάρτησης. Όπως θα δείτε στο εξαιρετικό blog post του Wes Dyer (πολλά thanx στον Palladin, μέσω του blog του οποίου γνώρισα το blog του Wes Dyer), αναφέρεται

But our C# workaround doesn’t really use recursion.  Recursion requires that a function calls itself.  The fib function really just invokes the delegate that the local variable fib references.  It may seem that this is just nit picking about words, but there is a difference.

Το οποίο μπορείτε να το διαπιστώσετε άμα εκτελέσετε τον κώδικα που έχει ακριβώς από κάτω από το παραπάνω

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n – 1) + fib(n – 2) : n;
Func<int, int> fibCopy = fib;
Console.WriteLine(fib(6));                        // displays 8
Console.WriteLine(fibCopy(6));                    // displays 8
fib = n => n * 2;
Console.WriteLine(fib(6));                        // displays 12
Console.WriteLine(fibCopy(6));                    // displays 18

Γιατί θα αποτύχει το παραπάνω; Το fib στην 6η γραμμή μας γυρνάει n * 2. Οπότε, πολύ σωστά, το fib(6) στην 7η γραμμή θα δώσει 12. Στην 8η γραμμή, όμως, το fibCopy δείχνει στο “παλιό” fib, στη 2η γραμμή. Όμως, το fib εκεί πλέον γυρνάει n * 2!! Άρα το fibCopy πλέον θα είναι

fibCopy(n) = n => n > 1 ? (n-1) * 2 + (n-2) * 2 : n;

Και εφόσον το n είναι 6, η fibCopy θα μας γυρίσει (6-1) * 2 + (6-2) * 2, δηλαδή 18, όπως έχει γράψει και ο Wes παραπάνω.Για όσους ενδιαφέρονται, στο blog post του Wes υπάρχει μια ιδανική υλοποίηση “ανώνυμης” αναδρομής.

Συνεχίζοντας με το post του Mark, εξίσου ενδιαφέρουσα είναι και η F# υλοποίηση

let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)

Μικρούλι, έτσι; Με την λέξη let στην F# δηλώνουμε έναν “τύπο”, με το rec του λέμε ότι είναι αναδρομικός, και μετά είναι το απλό if/else syntax.

Τέλος, μπορείτε να δείτε υπολογισμό Fibonacci όρων με χρήση της ThreadPool εδώ αλλά και να διαβάσετε τα comments στο post του Mark, θα δείτε και άλλες υλοποιήσεις με διάφορες μεθόδους και γλώσσες!!