Scheme 2: η IF και η φρικαλέα αναδρομή

IF:

Η δομή if-then-else είναι μία από τις πιο κοινές εκφράσεις στις γλώσσες προγραμματισμού. Η ακριβής σύνταξή της μπορεί να διαφέρει από γλώσσα σε γλώσσα, αλλά τα βασικά της στοιχεία είναι σχεδόν πάντα τα ίδια. Αποτελείται από τρία βασικά κομμάτια:

if [συνθήκη] then
        [κάνε κάτι]
else
        [κάνε κάτι άλλο]

τα οποία στη Scheme γράφονται λιγάκι διαφορετικά:

(if (συνθήκη)
   (κάνε κάτι)
   (κάνε κάτι άλλο)
)

Όταν η γλώσσα προγραμματισμού συναντήσει κάποιο if, περιμένει να ακολουθήσει μια boolean έκφραση, δηλαδή μια λογική πράξη που θα έχει ως αποτέλεσμα την τιμή ΑΛΗΘΕΣ ή ΨΕΥΔΕΣ. Αυτή τη λογική πράξη τη λέμε και συνθήκη της if. Λογικές πράξεις είναι η σύγκριση αριθμών, η σύγκριση μεταβλητών μεταξύ τους για ισότητα ή κάτι πιο πολύπλοκο όπως πχ το αν μια λίστα περιλαμβάνει ένα συγκεκριμένο στοιχείο. Το (3>5) είναι μια λογική πράξη με αποτέλεσμα ΨΕΥΔΕΣ. Το (x=y) είναι μια λογική πράξη που θα δώσει αποτέλεσμα ΑΛΗΘΕΣ αν το x είναι ίσο με το y και ΨΕΥΔΕΣ αν δεν είναι.

Αν η συνθήκη είναι αληθής, τότε θα εκτελεστεί το 'κάνε κάτι', αλλιώς θα εκτελεστεί το 'κάνε κάτι άλλο'. Για παράδειγμα:

(if ( < degree 5) 
 (display “Δεν περάσατε το μάθημα”) 
 (display “Περάσατε το μάθημα”) 
)

Αν η μεταβλητή degree είναι μικρότερη του 5, εκτελείται η πρώτη εντολή (και δεν περνάτε), αλλιώς εκτελείται η δεύτερη εντολή (και περνάτε). Αν δεν έγινε κατανοητό το παράδειγμα, μάλλον θα εκτελεστεί η πρώτη εντολή. :P

Πάνω σε αυτή τη λογική μπορούμε να χτίσουμε πιο πολύπλοκες εκφράσεις. Αντί να εκτελέσουμε μόνο μια εντολή σε κάθε περίπτωση, μπορούμε να εκτελέσουμε περισσότερες με χρήση του begin. Το begin ομαδοποιεί πολλές εντολές έτσι, ώστε το if (ή άλλες δομές) να τις εκτελέσει ως μία εντολή. Για παράδειγμα:

(if (< degree 5) 
 (begin 
  (display “Δεν περάσατε το μάθημα.”)
  (display “Δοκιμάστε ξανά του χρόνου.”)
 )  
 (begin 
  (display “Περάσατε το μάθημα.”) 
  (display “Για πτυχίο θέλετε ακόμα....”)
 ) 
)

Επίσης, μπορούμε να βάλουμε μία ή περισσότερες if μέσα σε μια άλλη if. Δηλαδή:

(if (< degree 5) 
 (display “Δεν περάσατε το μάθημα”) 
 (if (< degree 8)
  (display “Περάσατε με βαθμό: Καλώς”)
  (display “Περάσατε με βαθμό: Άριστα”)  
 ) 
)

Αν η degree είναι μικρότερη του 5, θα τυπωθεί το “Δεν περάσατε το μάθημα” και θα σταματήσει η εκτέλεση του προγράμματος. Αν η degree δεν είναι μικρότερη του 5, θα εκτελεστεί το δεύτερο σκέλος της if (αυτό που είναι στις γραμμές 3-6), το οποίο περιέχει μια δεύτερη if, η οποία θα τυπώσει το κατάλληλο μήνυμα ανάλογα με το αν η degree είναι μικρότερη ή όχι του 8.

Κάτι το οποίο αξίζει να προσέξετε στην προκειμένη περίπτωση είναι το ότι αν εκτελεστεί η δεύτερη if (γραμμή 3), αυτό σημαίνει ότι ΣΙΓΟΥΡΑ η degree είναι μεγαλύτερη ή ίση του 5, αφού βρισκόμαστε στην περίπτωση που η συνθήκη της πρώτης if (γραμμή 1) έχει δώσει ΨΕΥΔΕΣ.

Φυσικά, μπορούμε να βάζουμε όσες if θέλουμε τη μία μέσα στην άλλη.

Αναδρομή (recursion)

Στη σχολή αλεξιπτωτιστών, ο εκπαιδευτής δίνει οδηγίες στο νέο ο οποίος ετοιμάζεται αγχωμένος και φοβισμένος για την παρθενική του πτώση:

ΕΚΠΑΙΔΕΥΤΗΣ: Λοιπόν, τα κατάλαβες; Πηδάς από το αεροπλάνο στα 4000 μέτρα και το αλεξίπτωτο θα ανοίξει μόνο του.

ΝΕΟΣ: Εντάξει, αλλά τι γίνεται αν δεν ανοίξει και βρίσκομαι στα 3000 μέτρα;

Ε: Δε θα γίνει κάτι τέτοιο, αλλά αν γίνει θα τραβήξεις το σκοινί του αλεξίπτωτου και θα ανοίξει.

Ν: Και αν δεν ανοίξει και είμαι στα 2000 μέτρα;

Ε: Θα πατήσεις το κουμπί ασφαλείας του αλεξίπτωτου και θα ανοίξει.

Ν: Και αν δεν ανοίξει και είμαι στα 1000 μέτρα;

Ε: Θα τραβήξεις το σκοινί του εφεδρικού αλεξίπτωτου και θα ανοίξει το εφεδρικό.

Ν: Και αν δεν ανοίξει και είμαι στα 200 μέτρα;

Ε: Θα πατήσεις το κουμπί ασφαλείας του εφεδρικού και θα ανοίξει.

Ν: Και αν δεν ανοίξει και είμαι στα 2 μέτρα;

Ε: Καλά, ρε φίλε, είσαι σοβαρός; Δεν μπορείς να πηδήξεις από 2 μέτρα;

Η αναδρομή είναι μια τεχνική στον προγραμματισμό που ακολουθεί μια παρόμοια τακτική με τον εκπαιδευτή αλεξιπτωτιστών. Όταν είμαστε αντιμέτωποι με ένα δύσκολο και πολύπλοκο πρόβλημα, αντί να προσπαθήσουμε να το λύσουμε ευθέως, το ψευτο-λύνουμε με το να το αντικαθιστούμε με ένα παρόμοιο πρόβλημα, το οποίο είναι, κατά ελάχιστα, λιγότερο πολύπλοκο. Αυτό το δεύτερο, λιγότερο πολύπλοκο πρόβλημα το ψευτο-λύνουμε πάλι με ένα άλλο, κατά ελάχιστα, λιγότερο πολύπλοκο πρόβλημα. Αν συνεχίσουμε να ψευτο-λύνουμε κάθε πρόβλημα με ένα άλλο, λιγότερο πολύπλοκο, κάποια στιγμή θα καταλήξουμε σε ένα κατά πολύ πιο απλό πρόβλημα, το οποίο θα είναι τόσο απλό και στοιχειώδες, όσο και το να πηδάς από τα 2 μέτρα (χωρίς να γίνεις κιμάς όμως).

Ας πούμε ότι πρέπει να χτίσουμε έναν τοίχο με 10 σειρές τούβλα. Η μία προσέγγιση είναι να ξεκινήσουμε να βάλουμε την πρώτη σειρά τούβλα, μετά τη δεύτερη, μετά την τρίτη, μέχρι να φτάσουμε στη δέκατη. Η αναδρομική προσέγγιση είναι να κάνουμε την πάπια και να αρνηθούμε να κοιτάξουμε το πρόβλημα κατάματα. Αντ' αυτού, ανακοινώνουμε υπερήφανα με στεντόρεια φωνή: “Ένας τοίχος με 10 σειρές τούβλα; Παιχνιδάκι: παίρνουμε έναν τοίχο με 9 σειρές τούβλα και απλά προσθέτουμε μια σειρά τούβλα”. Με τον τρόπο αυτό, (ψευτο)λύσαμε το αρχικό πρόβλημα με το να επέμβουμε ελάχιστα (βάλαμε μια σειρά τούβλα) σε ένα κατά ελάχιστα λιγότερο πολύπλοκο πρόβλημα (ένας τοίχος με 9 σειρές τούβλα). Επειδή όμως οι εργοδότες μας δεν έμειναν ικανοποιημένοι και ρωτάνε από πού ξεφύτρωσε ο τοίχος με τα 9 τούβλα, τους κάνουμε τη χάρη και απαντάμε: “Θα πάρουμε έναν τοίχο με 8 τούβλα και θα προσθέσουμε μία σειρά ακόμα. Έλεος!”. Επειδή έχουμε μπλέξει με ηλίθιους που δεν καταλαβαίνουν, οι εργοδότες επιμένουν και εμείς απαντάμε με την ίδια συλλογιστική. Με τα πολλά, φτάνουμε να μας ρωτάνε πού θα βρούμε έναν τοίχο με μία σειρά τούβλα. Η απάντηση είναι πλέον τόσο στοιχειώδης που δεν αξίζει να ασχολούμαστε άλλο μαζί τους.

Με άλλα λόγια, στην αναδρομή λύνουμε ένα πρόβλημα με το να το αποφεύγουμε να το λύσουμε (αλλά με στυλ) μέχρι να βαρεθεί και να σταματήσει να είναι τόσο πολύπλοκο. Κάτι σαν “εγώ το λέω στο σκύλο μου και ο σκύλος στην ουρά του” (αλλά στο τέλος να δουλεύει).

Μπορούμε να πούμε ότι η αναδρομή είναι μια διαδικασία η οποία, με κάποιο τρόπο, αναφέρεται στον εαυτό της. Η διαδικασία αυτή δε χρειάζεται απαραίτητα να είναι κώδικας σε γλώσσα προγραμματισμού ή κάποια μαθηματική συνάρτηση. Ένας τύπος που κρατάει μια φωτογραφία του εαυτού του να κρατάει μια φωτογραφία του εαυτού του να κρατάει μια φωτογραφία του εαυτού του να κρατάει μια φωτογραφία του εαυτού του να κρατάει μια φωτογραφία του εαυτού του, κλπ, είναι μια αναδρομή.

Μερικά από τα (καμμένα) ακρωνύμια της πληροφορικής είναι επίσης αναδρομές. Η γλώσσα προγραμματισμού PHP σημαίνει “PHP: Hypertext Preprocessor”. Η οικογένεια λειτουργικών συστημάτων GNU σημαίνει "GNU's Not Unix". Ναι, εντάξει, ξέρω, είμαστε τελείως κατεστραμμένοι!

Αναδρομή υπάρχει και στα μαθηματικά. Για παράδειγμα, το παραγοντικό ενός θετικού ακεραίου αριθμού n ορίζεται ως το γινόμενο:

n! = n(n-1)(n-2)...1

ή αλλιώς

Το f(n) ισούται με το n επί το f(n-1). Για να βρούμε, δηλαδή το παραγοντικό του 5, το 5! ή αλλιώς f(5) έχουμε:

f(5) = 5 * f(4)

= 5 * 4 * f(3)

= 5 * 4 * 3 * f(2)

= 5 * 4 * 3 * 2 * f(1)

= 5 * 4 * 3 * 2 * 1

Δοκιμάστε να το κάνετε συνάρτηση στη Scheme (χωρίς να κοιτάτε τη λύση που ακολουθεί)

(define (f n)
   (if (= n 0)
       1
       (* n (f (- n 1)))
   )
)

(σημείωση: η λύση αυτή δουλεύει, την άφησα έτσι γιατί είναι πιο απλό, αλλά μπορεί να παρουσιάσει πρόβλημα σε κάποιες περιπτώσεις, μπορείτε να το βρείτε;)

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

(define (f n)
     (* n (f (- n 1)))
)

Θα χρειαστεί να πατήσετε το STOP αν το τρέξετε γιατί δεν πρόκειται να σταματήσει. Σε εμένα κόλλησε και έκλεισε η Scheme μόνη της. Γι'αυτό το λόγο, ΠΑΝΤΑ ΒΑΖΟΥΜΕ ΣΗΜΕΙΟ ΕΞΟΔΟΥ.

Ένα άλλο παράδειγμα από τα μαθηματικά είναι η ακολουθία fibonacci.

Μπορείτε να τη φτιάξετε στη Scheme; Περιμένω την απάντηση στα σχόλια.

Μια άλλη εφαρμογή της αναδρομής είναι οι πύργοι του Ανόι. Μπορείτε να βρείτε μια σχετική εφαρμογή του εδώ.

Αυτά. Αν έχω κάνει κανένα λάθος πουθενά, δικαιολογούμαι λόγω της ώρας.

Περιμένω απορίες και/ή τις λύσεις των παραπάνω ερωτήσεων.