Πώς να δημιουργήσετε μια διαίσθηση για αναδρομή

Και πώς να το χρησιμοποιήσετε για την επίλυση προβλημάτων

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

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

Τι είναι η αναδρομή;

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

f (x) = 2χ

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

A (n) = 2n

Οι ακολουθίες μπορούν να θεωρηθούν ως συναρτήσεις με εισόδους και εξόδους που περιορίζονται μόνο σε θετικούς ακέραιους αριθμούς. Γενικά, οι ακολουθίες ξεκινούν με 1. Αυτό σημαίνει ότι το Α (0) είναι 1. Η παραπάνω ακολουθία είναι η ακόλουθη:

A (n) = 1, 2, 4, 6, 8, 10,… όπου n = 0, 1, 2, 3, 4, 5,…

Τώρα, εξετάστε την ακόλουθη ακολουθία:

A (n) = 2 x A (n-1)

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

A (n) = 1, 2, 4, 8, 16,… όπου n = 0, 1, 2, 3, 4,…

Κάθε στοιχείο ορίζεται ως 2 φορές το προηγούμενο στοιχείο.

  • Το στοιχείο n = 4, 16, ορίζεται ως 2 φορές το προηγούμενο στοιχείο.
  • Το στοιχείο n = 3, 8, ορίζεται ως 2 φορές το προηγούμενο στοιχείο.
  • Το στοιχείο n = 2, 4, ορίζεται ως 2 φορές το προηγούμενο στοιχείο.
  • Το στοιχείο n = 1, 2, ορίζεται ως 2 φορές το προηγούμενο στοιχείο.
  • Το στοιχείο n = 0, 1, ορίζεται ως…

Το στοιχείο n = 0 δεν μπορεί να οριστεί αναδρομικά. Δεν υπάρχει προηγούμενο στοιχείο. Αυτό το ονομάζουμε βασική υπόθεση και είναι απαραίτητη συνέπεια των αναδρομικών ορισμών. Πρέπει να απεικονίζονται ρητά στον κωδικό σας . Θα μπορούσαμε να αναπαραστήσουμε αυτήν την αναδρομική ακολουθία στην Java όπως:

public int A(int n){ if (n == 0) return 1; return 2 * A(n - 1);}

Θα πρέπει να εξοικειωθείτε με την ανατομία μιας αναδρομικής μεθόδου. Σημειώστε τη βασική περίπτωση: εάν το n είναι 0, το στοιχείο ορίζεται ως 1. Διαφορετικά, το στοιχείο ορίζεται ως 2 φορές το προηγούμενο στοιχείο. Πρέπει να καλέσουμε αναδρομικά τη μέθοδο για να λάβουμε την τιμή του προηγούμενου στοιχείου και στη συνέχεια να την πολλαπλασιάσουμε με 2. Όλες οι αναδρομικές μέθοδοι θα έχουν αυτά τα δύο συστατικά:

  • Βασική περίπτωση, η οποία επιστρέφει μια καλά καθορισμένη τιμή.
  • Αναδρομική περίπτωση, η οποία επιστρέφει μια αναδρομικά καθορισμένη τιμή.

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

F (n) = 1, 1, 2, 3, 5, 8,… όπου n = 0, 1, 2, 3, 4, 5,…

  • Το n = 5, στοιχείο, 8, ορίζεται ως το άθροισμα του στοιχείου n = 4 και του στοιχείου n = 3…

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

  • Το στοιχείο n = 4, 5, ορίζεται ως το άθροισμα του στοιχείου n = 3 και του στοιχείου n = 2.
  • Το στοιχείο n = 3, 3, ορίζεται ως το άθροισμα του στοιχείου n = 2 και του στοιχείου n = 1.
  • Το στοιχείο n = 2, 2, ορίζεται ως το άθροισμα του στοιχείου n = 1 και του στοιχείου n = 0.
  • Το στοιχείο n = 1, 1, ορίζεται ως το άθροισμα του στοιχείου n = 0 και…

Το στοιχείο n = 1 δεν μπορεί να οριστεί αναδρομικά. Ούτε το στοιχείο n = 0. Αυτά τα στοιχεία δεν μπορούν να οριστούν αναδρομικά επειδή ο αναδρομικός ορισμός απαιτεί δύο προηγούμενα στοιχεία. Το στοιχείο n = 0 δεν έχει προηγούμενα στοιχεία και το στοιχείο n = 1 έχει μόνο ένα προηγούμενο στοιχείο. Αυτό σημαίνει ότι υπάρχουν δύο βασικές περιπτώσεις. Πριν γράψω οποιονδήποτε κωδικό, θα έγραφα κάτι σαν αυτό:

Το στοιχείο n = 0 ορίζεται ως 1. Το στοιχείο n = 1 ορίζεται ως 1.

Το στοιχείο n ορίζεται ως το άθροισμα του στοιχείου n-1 και του στοιχείου n-2.

Τώρα έχουμε μια ιδέα για το πώς αυτή η εργασία ορίζεται αναδρομικά και μπορούμε να προχωρήσουμε και να γράψουμε κάποιον κώδικα. Ποτέξεκινήστε να γράφετε κώδικα χωρίς πρώτα να έχετε μια φυσική κατανόηση της εργασίας.

public int F(int n) if (n == 0 

Η στοίβα κλήσης

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

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

The call stack (and stacks in general) function as you might imagine some sort of real-life stack would. Imagine a stack of papers on your desk — it starts as nothing, and then you add papers one by one. You don’t know anything about any of the papers in the stack except for the paper on top. The only way you can remove papers from the stack is by taking them off the top, one-by-one, in the opposite order that they were added.

This is essentially how the call stack works, except the items in the stack are activation records instead of papers. Activation records are just little pieces of data that store the method name and parameter values.

Without recursion, the call stack is pretty simple. Here’s an example. If you had some code that looked like this…

public static void main(String[] args) System.out.println(myMethod(1));

…The call stack would look like this:

* myMethod(int a)
* main(String[] args)

Here we see two methods under execution, main and myMethod. The important thing to notice is that main cannot be removed from the stack until myMethod is removed from the stack. In other words, main cannot complete until myMethod is called, executed, and returns a value.

This is true for any case of method composition (a method within a method) — so let’s look at recursive example: the A(int n) method we wrote earlier. Your code might look like this:

public static void main(String[] args) System.out.println(A(4));
public static int A(int n){ if (n == 0) return 1; return 2 * A(n - 1);}

When main is called, A is called. When A is called, it calls itself. So the call stack will start building up like so:

* A(4)* main(String[] args)

A(4) calls A(3).

* A(3)* A(4)* main(String[] args)

Now, it’s important to note that A(4) cannot be removed from the call stack until A(3) is removed from the call stack first. This makes sense, because the value of A(4) depends on the value of A(3). The recursion carries on…

* A(0)* A(1)* A(2)* A(3)* A(4)* main(String[] args)

When A(0) is called, we have reached a base case. This means that the recursion is completed, and instead of making a recursive call, a value is returned. A(0) comes off the stack, and the rest of the calls are then able to come off the stack in succession until A(4) is finally able to return its value to main.

Here’s the intuition: the return value of any method call depends on the return value of another method call. Therefore, all the method calls must be stored in memory until a base case is reached. When the base case is reached, the values start becoming well-defined instead of recursively defined. For example, A(1) is recursively defined until it knows the definition of the base case, 1. Then, it is well-defined as 2 times 1.

When we are trying to solve problems with recursion, it is often more effective to think about the order in which values are returned. This is the opposite of the order in which calls are made. This order is more useful because it consists of well-defined values, instead of recursively defined values.

For this example, it is more useful to consider that A(0) returns 1, and then A(1) returns 2 times 1, and then A(2) returns 2 times A(1), and so on. However, when we are writing our code, it can easier to frame it in the reverse order (the order that the calls are made). This is another reason that I find it helpful to write the base case and the recursive case down before writing any code.

Helper Methods and Recursion vs. Loops

We are programmers, not mathematicians, so recursion is simply a tool. In fact, recursion is a relatively simple tool. It’s very similar to loops in that both loops and recursion induce repetition in the program.

You may have heard that any repetitive task can be done using either a while loop or a for loop. Some tasks lend themselves better to while loops and other tasks lend themselves better to for loops.

The same is true with this new tool, recursion. Any repetitive task can be accomplished with either a loop or recursion, but some tasks lend themselves better to loops and others lend themselves better to recursion.

When we use loops, it is sometimes necessary to make use of a local variable to “keep track” of a calculation. Here’s an example.

public double sum (double[] a){ double sum = 0.0; for (int i = 0; i < a.length; i++) sum += a[i]; return sum;
}

This method takes an array of doubles as a parameter and returns the sum of that array. It uses a local variable, sum, to keep track of the working sum. When the loop is completed, sum will hold the actual sum of all values in the array, and that value is returned. This method actually has two other local variables that are less obvious. There is the double array a, whose scope is the method, and the iterator i (keeps track of the index), whose scope is the for loop.

What if we wanted to accomplish this same task using recursion?

public double recursiveSum(double[] a) # recursively calculate sum

This task is repetitive, so it is possible to do it using recursion, though it is probably more elegantly accomplished using a loop. We just need to create a few local variables to keep track of the working sum and the index, right?

Alas, this is impossible. Local variables only exist in the context of a single method call, and recursion makes use of repeated method calls to accomplish a repetitive task. This means that local variables are pretty much useless when we are using recursion. If you are writing a recursive method and you feel as though you need a local variable, you probably need a helper method.

A helper method is a recursive method that makes use of additional parameters to keep track of values. For recursiveSum, our helper method might look like this:

public double recursiveSum(double[] a, double sum, int index){ if (index == a.length) return sum; sum += a[index]; return recursiveSum(a, sum, index + 1);}

This method builds the sum by passing the working value to a new method call with the next index. When there are no more values in the array, the working sum is the actual sum.

Now we have two methods. The “starter method,” and the helper method.

public double recursiveSum(double[] a) # recursively calculate sum
public double recursiveSum(double[] a, double sum, int index){ if (index == a.length) return sum; sum += a[index]; return recursiveSum(a, sum, index + 1);}

The term “helper method” is actually a bit of a misnomer. It turns out that the helper method does all the work, and the other method is just a starter. It simply calls the helper method with the initial values that start the recursion.

public double recursiveSum(double[] a) return recursiveSum(a, 0.0, 0);
public double recursiveSum(double[] a, double sum, int index){ if (index == a.length) return sum; sum += a[index]; return recursiveSum(a, sum, index + 1);}

Note that the values used in the starter call to the helper method are the same values used to initialize the local variables in the loop example. We initialize the variable used to keep track of the sum to 0.0, and we initialize the variable used to keep track of the index to 0.

Earlier, I said that local variables are useless in the context of recursion. This isn’t completely true, because the method parameters are indeed local variables. They work for recursion because new ones are created every time the method is called. When the recursion is executed, there are many method calls being stored in the call stack, and as a result there are many copies of the local variables.

You might ask, “If the helper method does all the work, why do we even need the starter method? Why don’t we just call the helper method with the initial values, and then you only need to write one method?”

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

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

Τυλίγοντας

Η επανάληψη είναι μια αρκετά προκλητική ιδέα, αλλά τα καταφέρατε μέχρι το τέλος της εξήγησής μου. Ελπίζω να καταλάβετε τη μαγεία λίγο καλύτερα. Τώρα σας παραχωρώ επίσημα τον τίτλο "Grand-Wizard of Recursion". Συγχαρητήρια!