Εισαγωγή
Αναδρομή
Οι αναδρομικές συναρτήσεις είναι συναρτήσεις που καλούν τον εαυτό τους.
Μια αναδρομική συνάρτηση χρειάζεται να έχει τουλάχιστον μία βασική περίπτωση και τουλάχιστον μία αναδρομική περίπτωση.
Μια βασική περίπτωση επιστρέφει μια τιμή χωρίς να καλέσει ξανά τη συνάρτηση.
Μια αναδρομική περίπτωση καλεί ξανά τη συνάρτηση, τροποποιώντας την είσοδο ώστε κάποια στιγμή να ταιριάξει με τη βασική περίπτωση.
Ακολουθεί ένα παράδειγμα που μετράει τα στοιχεία ενός πίνακα.
def count:
if length == 0 then
0 # base case
else
1 + (.[1:] | count) # recursive case
end;
([] | count), # => 0
([11, 22, 33] | count) # => 3
Μια αναδρομική συνάρτηση μπορεί να έχει πολλές βασικές περιπτώσεις ή/και πολλές αναδρομικές περιπτώσεις.
Για παράδειγμα, η ακολουθία Fibonacci είναι μια αναδρομική ακολουθία με δύο βασικές περιπτώσεις.
def fibonacci:
if . == 0 then
0
elif . == 1 then
1
else
(. - 1 | fibonacci) + (. - 2 | fibonacci)
end;
10 | fibonacci # => 55
Η μέτρηση του αριθμού των εμφανίσεων μιας δεδομένης τιμής x σε μια λίστα έχει δύο αναδρομικές περιπτώσεις.
def count_occurrences(x):
if length == 0 then
0
elif first == x then
1 + (.[1:] | count_occurrences(x))
else
(.[1:] | count_occurrences(x))
end;
[11, 22, 33, 22, 44] | count_occurrences(22) # => 2
Στην πράξη, η επανάληψη πάνω σε λίστες και άλλες απαριθμήσιμες δομές δεδομένων γίνεται τις περισσότερες φορές με ενσωματωμένες συναρτήσεις,
όπως οι map και reduce, ή με ροές όπως [.[] | select(...)].
Εσωτερικά, μερικές ενσωματωμένες συναρτήσεις είναι υλοποιημένες με αναδρομή.
Οδηγίες
Μόλις μπήκες σε μια ομάδα που συντηρεί ένα pipeline δεδομένων βασισμένο στο jq.
Στην πρώτη σου συνεδρία προγραμματισμού σε ζεύγη, ο νέος σου συνάδελφος αρχίζει να αναρωτιέται:
"Ξέρεις πώς λειτουργούν εσωτερικά τα add, reverse και map; Ας το εξερευνήσουμε. Δοκίμασε να τα υλοποιήσεις μόνος σου με αναδρομή, χωρίς τα ενσωματωμένα φίλτρα."
1. Υλοποίησε μια συνάρτηση που προσθέτει τους αριθμούς ενός πίνακα
Θα ξαναϋλοποιήσουμε το ενσωματωμένο φίλτρο add για να εξασκηθούμε στην αναδρομή.
Η βασική περίπτωση είναι ότι ένας κενός πίνακας έχει άθροισμα μηδέν.
Υλοποίησέ το μόνος σου με μια αναδρομική συνάρτηση, μη χρησιμοποιήσεις το ενσωματωμένο add.
[5, 4, 6, 10] | array_add # => 25
2. Αντιστρέψε έναν πίνακα
Θα ξαναϋλοποιήσουμε το ενσωματωμένο φίλτρο reverse.
Η βασική περίπτωση είναι ότι ένας κενός πίνακας αντιστρέφεται σε έναν κενό πίνακα.
Υλοποίησέ το μόνος σου με μια αναδρομική συνάρτηση, μη χρησιμοποιήσεις το ενσωματωμένο reverse.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. Εφάρμοσε map σε έναν πίνακα
Θα ξαναϋλοποιήσουμε το ενσωματωμένο φίλτρο map.
Η συνάρτηση παίρνει ένα φίλτρο ως παράμετρο, εκτελεί αυτό το φίλτρο για κάθε στοιχείο του πίνακα εισόδου και επιστρέφει τα αποτελέσματα σε έναν νέο πίνακα.
Η βασική περίπτωση είναι ότι ένας κενός πίνακας αντιστοιχίζεται σε έναν κενό πίνακα.
Υλοποίησέ το μόνος σου με μια αναδρομική συνάρτηση, μη χρησιμοποιήσεις το ενσωματωμένο map.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Άσκηση εκμάθησης
