Αναδρομή σε

Σχετικά με την έννοια Αναδρομή

Οι αναδρομικές συναρτήσεις είναι συναρτήσεις που καλούν τον εαυτό τους.

Μια αναδρομική συνάρτηση πρέπει να έχει τουλάχιστον μία βασική περίπτωση και τουλάχιστον μία αναδρομική περίπτωση.

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

Ακολουθεί ένα παράδειγμα που μετρά τα στοιχεία ενός πίνακα.

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, ή με τη χρήση streams όπως το [.[] | select(...)]. Κάτω από το καπό, ορισμένες ενσωματωμένες συναρτήσεις είναι υλοποιημένες με αναδρομή.

Άπειρη αναδρομή

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

Αυτό το πρόβλημα της άπειρης αναδρομής μπορεί να προκληθεί από:

• Το να ξεχάσεις να υλοποιήσεις μια βασική περίπτωση.
• Το να μην ορίσεις τη βασική περίπτωση ως την πρώτη ρήτρα.
• Το να μην τροποποιήσεις σωστά το όρισμα κατά την αναδρομική κλήση, κι έτσι να μη φτάσεις ποτέ στη βασική περίπτωση.

Βελτιστοποίηση τελικής κλήσης

Όπως περιγράφεται στη Wikipedia:

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

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

Ορισμένες γλώσσες υλοποιούν βελτιστοποίηση τελικής κλήσης, ώστε η τελική κλήση να μπορεί να επαναχρησιμοποιήσει το τρέχον πλαίσιο στοίβας αντί να προσθέσει ένα νέο πλαίσιο στη στοίβα κλήσεων. Αυτό μπορεί να προσφέρει οφέλη στην απόδοση πέρα από την προστασία απέναντι στην τρομερή υπερχείλιση στοίβας.

Το jq υλοποιεί βελτιστοποίηση τελικής κλήσης, αλλά μόνο για συναρτήσεις με 0 ορίσματα. Ο τρόπος για να το εκμεταλλευτείς αυτό είναι να ορίσεις μια "εσωτερική" συνάρτηση με 0 ορίσματα που παίρνει κάποια κατάσταση ως είσοδο. Η εσωτερική συνάρτηση μπορεί να τροποποιήσει την κατάσταση όπως χρειάζεται και να περάσει τη νέα κατάσταση στην τελική αναδρομική κλήση. Η εξωτερική συνάρτηση δημιουργεί την αρχική κατάσταση και τη δίνει στην εσωτερική συνάρτηση για να ξεκινήσει η αναδρομή.

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

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55