Αναδρομή — Πώς λειτουργεί, παραδείγματα και βασικές περιπτώσεις

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

Αν χρειάζεσαι μόνο τη βασική ιδέα, είναι η εξής: η αναδρομή παύει να είναι χρήσιμη τη στιγμή που ο κανόνας των μικρότερων βημάτων δεν οδηγεί πλέον σε ένα έγκυρο σημείο τερματισμού.

Τι σημαίνει η αναδρομή στα μαθηματικά

Ένας αναδρομικός ορισμός δεν απαριθμεί κάθε περίπτωση ξεχωριστά. Αντί γι’ αυτό, δίνει ένα σημείο εκκίνησης και έναν κανόνα για να κατασκευάζουμε μεγαλύτερες περιπτώσεις από μικρότερες.

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

Γιατί απαιτείται μια βασική περίπτωση

Η βασική περίπτωση είναι το σημείο τερματισμού. Χωρίς αυτήν, ο ορισμός συνεχίζει να παραπέμπει σε όλο και μικρότερες περιπτώσεις χωρίς να ολοκληρώνεται ποτέ.

Η βασική περίπτωση πρέπει επίσης να ταιριάζει με τον κανόνα που επέλεξες. Αν το αναδρομικό βήμα μειώνει από το $n$ στο $n-1$, τότε η βασική περίπτωση πρέπει να είναι προσβάσιμη από αυτό το μοτίβο για τις εισόδους που επιτρέπεις.

Λυμένο παράδειγμα: αναδρομή του παραγοντικού

Το παραγοντικό είναι ένας κλασικός αναδρομικός ορισμός. Για ακέραιους αριθμούς $n \ge 0$, ορίζουμε το παραγοντικό ως

$$0! = 1$$

και, για $n \ge 1$,

$$n! = n(n-1)!$$

Εδώ, το $0! = 1$ είναι η βασική περίπτωση και το $n! = n(n-1)!$ είναι το αναδρομικό βήμα.

Για να βρούμε το $4!$, συνεχίζουμε να μειώνουμε μέχρι να εμφανιστεί η βασική περίπτωση:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

Τώρα εφαρμόζουμε τη βασική περίπτωση $0! = 1$:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

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

Αναδρομή vs. σχέση αναδρομής

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

Για παράδειγμα, η ακολουθία Fibonacci δίνεται από μια σχέση αναδρομής, επειδή κάθε όρος ορίζεται από προηγούμενους όρους. Το παραγοντικό είναι επίσης αναδρομικό, αλλά συνήθως παρουσιάζεται ως αναδρομικός ορισμός μιας συνάρτησης και όχι ως σχέση αναδρομής για μια ακολουθία.

Συνηθισμένα λάθη στην αναδρομή

Παράλειψη της βασικής περίπτωσης

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

Χρήση βήματος που δεν μικραίνει

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

Παράβλεψη της συνθήκης του κανόνα

Στο παράδειγμα του παραγοντικού, ο κανόνας $n! = n(n-1)!$ χρησιμοποιείται για $n \ge 1$. Αυτή η συνθήκη έχει σημασία. Χωρίς αυτήν, θα μπορούσες να προσπαθήσεις να εφαρμόσεις τον κανόνα εκεί όπου ο ορισμός δεν προοριζόταν να ισχύει.

Η υπόθεση ότι η αναδρομή είναι μόνο ιδέα του προγραμματισμού

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

Πότε είναι χρήσιμη η αναδρομή

Η αναδρομή είναι χρήσιμη όταν ένα πρόβλημα διασπάται φυσικά σε μικρότερες εκδοχές του εαυτού του. Τη συναντάς στα παραγοντικά, στις ακολουθίες τύπου Fibonacci, στα αναδρομικά ορισμένα σύνολα και σε πολλούς αλγορίθμους.

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

Ένας γρήγορος έλεγχος για έναν σωστό αναδρομικό ορισμό

Κάνε δύο ερωτήσεις:

1. Έχω βασική περίπτωση;
2. Κάθε αναδρομικό βήμα με φέρνει πιο κοντά σε αυτήν;

Αν η απάντηση σε κάποια από τις δύο είναι όχι, ο ορισμός χρειάζεται διόρθωση.

Δοκίμασε ένα παρόμοιο πρόβλημα

Όρισε μια ακολουθία ως

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

και μετά βρες τα $a_2$, $a_3$ και $a_4$. Είναι ένας γρήγορος τρόπος να εξασκηθείς στον εντοπισμό της βασικής περίπτωσης και του αναδρομικού βήματος σε ένα νέο πλαίσιο.