Πιο σύνθετες μορφές αναδρομής

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

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

για σπειροειδές :βήμα
αν :βήμα > 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 ολοκληρώνεται

Είναι δύσκολο να σκέφτεστε κατά τη διάρκεια των αναδρομικών περιγραφών. Χρειάζεται εξάσκηση. Ωστόσο, αξίζει να εξοικειωθείτε με αυτή την έννοια. Οι αναδρομικοί ορισμοί μπορούν να είναι περιεκτικοί και ευπαρουσίαστοι. Η διαδικασία δέντρο είναι φαινομενικά απλή, αλλά οι διακλαδώσεις της είναι ιδιαίτερα περίπλοκες. Σε αυτή τη διαδικασία δέντρο, η κατάσταση διαφάνειας (δηλαδή, όταν η αρχική και τελική κατάσταση της χελώνας είναι ίδιες) είναι ιδιαίτερα σημαντική: οι τελικές κινήσεις πίσω και αριστερά επαναφέρουν τη χελώνα στην αρχική της θέση και κατεύθυνση, έτσι ώστε όλα τα δέντρα να ταιριάζουν μεταξύ τους.