Πιο σύνθετες μορφές αναδρομής
Μέχρι στιγμής, όλες οι αναδρομικές διαδικασίες που έχουμε δει έχουν την κλήση αναδρομικής διαδικασίας ως τελική τους οδηγία. Η αναδρομή αυτή ονομάζεται ουραία αναδρομή. Μπορούμε να τη δούμε ως μια γενική επανάληψη, όπου η οδηγία εκτελείται συνεχώς.
Οι πιο σύνθετες αναδρομές περιέχουν μία ή περισσότερες οδηγίες μετά την αναδρομική γραμμή. Ένα απλό παράδειγμα αποτελεί μια άλλη μορφή της διαδικασίας πολυσπείρα.
για σπειροειδές :βήμα
αν :βήμα > 50 [στοπ]
μπροστά :βήμα
δεξιά 90
σπειροειδές :βήμα + 5
μπροστά :βήμα
αριστερά 90
τέλοςΠαρατηρήστε πως υπάρχουν δύο οδηγίες μετά την αναδρομική γραμμή: μπροστά και αριστερά.
σπειροειδές5Για να εξετάσετε τη διεργασία, μπορείτε να δώσετε μεγαλύτερη τιμή στο σπειροειδές:
σπειροειδές40Να θυμάστε πως, όταν σταματήσει μια υποδιαδικασία σπειροειδές (όταν το :βήμα είναι μεγαλύτερο του 50), η υπερδιαδικασία δεν διακόπτεται αμέσως. Πρέπει πρώτα να ολοκληρωθεί η εκτέλεση των υπόλοιπων οδηγιών κάθε υποδιαδικασίας, πριν από τη διακοπή της. Κάθε σπειροειδές διατηρεί την τιμή του για το :βήμα. Κάθε σπειροειδές εκτελεί το μπροστά με τις δικές του τιμές για το :βήμα και μετά το αριστερά 90.
Ένα παράδειγμα εκτέλεσης οδηγιών από το σπειροειδές μπορεί να έχει την ακόλουθη μορφή:
Το σπειροειδές 40 ξεκινά, το βήμα είναι 40
1. αν 40 > 50 [στοπ]
αλλά το 40 > 50 είναι ΛΑΘΟΣ
2. μπροστά 40
3. δεξιά 90
4. σπειροειδές 40 + 5Το σπειροειδές 45 ξεκινά, το βήμα είναι 45
1. αν 45 > 50 [στοπ]
αλλά το 45 > 50 είναι ΛΑΘΟΣ
2. μπροστά 45
3. δεξιά 90
4. σπειροειδές 45 + 5ααααααα Το σπειροειδές 50 ξεκινά, το βήμα είναι 50
1. αν 50 > 50 [στοπ]
αλλά το 50 > 50 είναι ΛΑΘΟΣ
2. μπροστά 50
3. δεξιά 90
4. σπειροειδές 50 + 5ααααααα ααααααα Το σπειροειδές 55 ξεκινά, το βήμα είναι 55
1. αν 55 > 50 [στοπ]
πράγματι το 55 > 50 είναι ΣΩΣΤΟ
το σπειροειδές 55 διακόπτεται
ααααααα ααααααα 5. μπροστά 50
6. αριστερά 90
το σπειροειδές 50 ολοκληρώνεται
ααααααα 5. μπροστά 45
6. αριστερά 90
το σπειροειδές 45 ολοκληρώνεται
5. μπροστά 40
6. αριστερά 90
το σπειροειδές 40 ολοκληρώνεται
Η διεργασία αυτή ακολουθεί τον εξής κανόνα:
Όταν καλείται μια διαδικασία, η υπερδιαδικασία περιμένει έως ότου ολοκληρωθεί η υποδιαδικασία και στη συνέχεια συνεχίζει με την επόμενη οδηγία μετά την κλήση.Ο κανόνας αυτός φαίνεται απλός, αλλά η κατάσταση μπορεί να γίνει πιο πολύπλοκη όταν:
- Υπάρχουν περισσότερες από μία αναδρομικές κλήσεις μέσα στην ίδια διαδικασία.
- Κάθε αναδρομική διαδικασία έχει τις δικές της τιμές για τις εισόδους της.
- Η σειρά εκτέλεσης είναι αντίστροφη προς την αναμενόμενη. Αυτό συμβαίνει επειδή η τελευταία κληθείσα διαδικασία είναι αυτή που σταματά πρώτη.
Ένα γνωστό σχετικό παράδειγμα είναι το δυαδικό δέντρο (Abelson, 1982). Η αναδρομική περιγραφή του δέντρου είναι ένα σχήμα μορφής V με ένα μικρότερο δέντρο σε κάθε άκρο. Κάθε μικρότερο δέντρο έχει ένα σχήμα μορφής V με ένα ακόμη πιο μικρό δέντρο σε κάθε άκρο του και ούτω καθεξής. Για παράδειγμα:
Οι οδηγίες για τη σχεδίαση κάθε σχήματος V σε αυτό το δέντρο θα έχει την εξής μορφή:
αριστερά 45
μπροστά :μήκος
πίσω :μήκος
δεξιά 90
μπροστά :μήκος
πίσω :μήκος
αριστερά 45
Αν υποθέσουμε ότι για το αναδρομικό μας δέντρο ισχύει πως κάθε δέντρο έχει στην κορυφή κάθε κλάδου ένα δέντρο μισού μεγέθους από το αρχικό, τότε η διαδικασία δέντρο θα καλεί τον εαυτό της μετά από κάθε οδηγία μπροστά, με το μισό του μήκους της:
για δέντρο :μήκος
αριστερά 45
μπροστά :μήκος
δέντρο :μήκος / 2
πίσω :μήκος
δεξιά 90
μπροστά :μήκος
δέντρο :μήκος / 2
πίσω :μήκος
αριστερά 45
τέλοςΑυτή η διαδικασία όμως δεν θα πετύχει γιατί δεν έχει οριστεί κανόνας διακοπής. Κάθε δέντρο που καλείται, θα συνεχίσει να εκτελείται χωρίς να ολοκληρώνει ποτέ τις οδηγίες του. Με έναν απλό κανόνα διακοπής θα μπορούσαμε να πετύχουμε τη διακοπή της διαδικασίας δέντρο όταν το :μήκος είναι πολύ μικρό:
για δέντρο :μήκος
αν :μήκος < 2 [στοπ]
αριστερά 45
μπροστά :μήκος
δέντρο :μήκος / 2
πίσω :μήκος
δεξιά 90
μπροστά :μήκος
δέντρο :μήκος / 2
πίσω :μήκος
αριστερά 45
τέλοςΤώρα δοκιμάστε το δέντρο.
δέντρο 40Σύμφωνα με το παραπάνω παράδειγμα, το δέντρο 12 θα κάνει τα εξής:
Το δέντρο 12 ξεκινά, το μήκος είναι 12
1. αν 12 < 2 [στοπ]
αλλά το 12 < 2 είναι ΛΑΘΟΣ
2. αριστερά 45
3. μπροστά 12
4. δέντρο 12 / 2Το δέντρο 6 ξεκινά, το μήκος είναι 6
1. αν 6 < 2 [στοπ]
αλλά το 6 < 2 είναι ΛΑΘΟΣ
2. αριστερά 45
3. μπροστά 6
4. δέντρο 6 / 2ααααααα Το δέντρο 3 ξεκινά, το μήκος είναι 3
1. αν 3 < 2 [στοπ]
αλλά το 3 < 2 είναι ΛΑΘΟΣ
2. αριστερά 45
3. μπροστά 3
4. δέντρο 3 / 2ααααααα ααααααα Το δέντρο 1.5 ξεκινά, το βήμα είναι 1.5
1. αν 1.5 < 2 [στοπ]
πράγματι 1.5 < 2 είναι ΣΩΣΤΟ
Το δέντρο 1.5 διακόπτεται
ααααααα ααααααα 5. πίσω 3
6. δεξιά 90
7. μπροστά 3
8. δέντρο 3 / 2ααααααα ααααααα Το δέντρο 1.5 ξεκινά, το βήμα είναι 1.5
1. αν 1.5 < 2 [στοπ]
πράγματι 1.5 < 2 είναι ΣΩΣΤΟ
Το δέντρο 1.5 διακόπτεται
ααααααα ααααααα 9. πίσω 3
10. αριστερά 45
Το δέντρο 3 ολοκληρώνεται
ααααααα 5. πίσω 6
6. δεξιά 90
7. μπροστά 6
8. δέντρο 6 /2ααααααα Το δέντρο 3 ξεκινά, το μήκος είναι 3
1. αν 3 < 2 [στοπ]
αλλά το 3 < 2 είναι ΛΑΘΟΣ
2. αριστερά 45
3. μπροστά 3
4. δέντρο 3 / 2
ααααααα ααααααα Το δέντρο 1.5 ξεκινά, το βήμα είναι 1.5
1. αν 1.5 < 2 [στοπ]
πράγματι 1.5 < 2 είναι ΣΩΣΤΟ
Το δέντρο 1.5 διακόπτεται
ααααααα ααααααα 5. πίσω 3
6. δεξιά 90
7. μπροστά 3
8. δέντρο 3 / 2ααααααα ααααααα
Το δέντρο 1.5 ξεκινά, το βήμα είναι 1.5
1. αν 1.5 < 2 [στοπ]
πράγματι 1.5< 2 είναι ΣΩΣΤΟ
Το δέντρο 1.5 διακόπτεται
ααααααα ααααααα 9. πίσω 3
10. αριστερά 45
Το δέντρο 3 ολοκληρώνεται
ααααααα 9. πίσω 6
10. αριστερά 45
Το δέντρο 6 ολοκληρώνεται
5. πίσω 12
6. δεξιά 90
7. μπροστά 12
8. δέντρο 12 / 2Το δέντρο 6 ξεκινά, το μήκος είναι 6
1. αν 6 < 2 [στοπ]
αλλά το 6 < 2 είναι ΛΑΘΟΣ
2. αριστερά 45
3. μπροστά 6
4. δέντρο 6 / 2ααααααα Το δέντρο 3 ξεκινά, το μήκος είναι 3
1. αν 3 < 2 [στοπ]
αλλά το 3 < 2 είναι ΛΑΘΟΣ
2. αριστερά 45
3. μπροστά 3
4. δέντρο 3 / 2ααααααα ααααααα
Το δέντρο 1.5 ξεκινά, το βήμα είναι 1.5
1. αν 1.5 < 2 [στοπ]
πράγματι 1.5 < 2 είναι ΣΩΣΤΟ
Το δέντρο 1.5 διακόπτεται
ααααααα ααααααα 5. πίσω 3
6. δεξιά 90
7. μπροστά 3
8. δέντρο 3 / 2ααααααα ααααααα Το δέντρο 1.5 ξεκινά, το βήμα είναι 1.5
1. αν 1.5 < 2 [στοπ]
πράγματι 1.5 < 2 είναι ΣΩΣΤΟ
Το δέντρο 1.5 διακόπτεται
ααααααα ααααααα 9. πίσω 3
10. αριστερά 45
Το δέντρο 3 ολοκληρώνεται
ααααααα 5.πίσω 6
6. δεξιά 90
7. μπροστά 6
8. δέντρο 6 / 2ααααααα Το δέντρο 3 ξεκινά, το μήκος είναι 3
1. αν 3 < 2 [στοπ]
αλλά το 3 < 2 είναι ΛΑΘΟΣ
2. αριστερά 45
3. μπροστά 3
4. δέντρο 3 / 2ααααααα ααααααα Το δέντρο 1.5 ξεκινά, το βήμα είναι 1.5
1. αν 1.5 < 2 [στοπ]
πράγματι 1.5 < 2 είναι ΣΩΣΤΟ
Το δέντρο 1.5 διακόπτεται
ααααααα ααααααα 5. πίσω 3
6. δεξιά 90
7. μπροστά 3
8. δέντρο 3 / 2ααααααα ααααααα Το δέντρο 1.5 ξεκινά, το βήμα είναι 1.5
1. αν 1.5 < 2 [στοπ]
πράγματι 1.5 < 2 είναι ΣΩΣΤΟ
Το δέντρο 1.5 διακόπτεται
ααααααα ααααααα 9. πίσω 3
10. αριστερά 45
Το δέντρο 3 ολοκληρώνεται
ααααααα 9. πίσω 6
10. αριστερά 45
Το δέντρο 6 ολοκληρώνεται
9. πίσω 12
10. αριστερά 45
Το δέντρο 12 ολοκληρώνεταιΕίναι δύσκολο να σκέφτεστε κατά τη διάρκεια των αναδρομικών περιγραφών. Χρειάζεται εξάσκηση. Ωστόσο, αξίζει να εξοικειωθείτε με αυτή την έννοια. Οι αναδρομικοί ορισμοί μπορούν να είναι περιεκτικοί και ευπαρουσίαστοι. Η διαδικασία δέντρο είναι φαινομενικά απλή, αλλά οι διακλαδώσεις της είναι ιδιαίτερα περίπλοκες. Σε αυτή τη διαδικασία δέντρο, η κατάσταση διαφάνειας (δηλαδή, όταν η αρχική και τελική κατάσταση της χελώνας είναι ίδιες) είναι ιδιαίτερα σημαντική: οι τελικές κινήσεις πίσω και αριστερά επαναφέρουν τη χελώνα στην αρχική της θέση και κατεύθυνση, έτσι ώστε όλα τα δέντρα να ταιριάζουν μεταξύ τους.