Αναδρομή σε

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

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

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

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

Πολύ συχνά, κάθε περίπτωση γράφεται στη δική της ρήτρα συνάρτησης.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

Μια αναδρομική συνάρτηση μπορεί να έχει πολλές βασικές περιπτώσεις ή/και πολλές αναδρομικές περιπτώσεις. Για παράδειγμα, η ακολουθία Φιμπονάτσι είναι μια αναδρομική ακολουθία με δύο βασικές περιπτώσεις:

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

Η μέτρηση του αριθμού των εμφανίσεων μιας δεδομένης τιμής x σε μια λίστα έχει δύο αναδρομικές περιπτώσεις:

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

Βρόχοι μέσω αναδρομής

Λόγω της αμεταβλητότητας, οι βρόχοι στην Elixir γράφονται διαφορετικά από ό,τι στις προστακτικές γλώσσες. Για παράδειγμα, οι βρόχοι συνήθως μοιάζουν κάπως έτσι:

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

Σε μια συναρτησιακή γλώσσα, η μεταβολή του i (καλώντας το i++) δεν είναι δυνατή. Έτσι, οι βρόχοι πρέπει να υλοποιούνται με αναδρομή.

Το αντίστοιχο ενός βρόχου for στην Elixir θα έμοιαζε κάπως έτσι:

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

Στην πράξη, η επανάληψη πάνω από λίστες και άλλες απαριθμήσιμες δομές δεδομένων γίνεται συνήθως με τη χρήση του module Enum. Κάτω από το καπό, οι συναρτήσεις του module Enum υλοποιούνται με αναδρομή.

Άπειρη εκτέλεση

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

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

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