Kuinka rakentaa intuitio rekursiota varten

Ja miten sitä käytetään ongelmien ratkaisemiseen

Rekursio on yksi pelottavimmista aiheista, joita opiskelijat kohtaavat ohjelmoinnissa. On vaikea ymmärtää, koska ihmisen aivot eivät kykene suorittamaan rekursiota - mutta tietokoneet ovat. Siksi rekursio on niin tehokas työkalu ohjelmoijille, mutta se tarkoittaa myös, että sen käytön oppiminen on äärimmäisen vaikeaa. Haluan auttaa sinua rakentamaan intuition rekursiota varten, jotta voit käyttää sitä ongelmien ratkaisemiseen.

Olen opettaja assistenttini tietojenkäsittelytieteen peruskurssille yliopistossa. Olen selittänyt rekursiota täsmälleen samalla tavalla tusina kertaa tällä viikolla. Selitykseni näyttää auttavan useimpia opiskelijoita. Tässä artikkelissa on yleisin selitys yläosassa ja tarkin selitys alaosassa. Näin voit aloittaa alusta ja lopettaa heti, kun tunnet ymmärtävän rekursiota riittävän hyvin. Olen toimittanut joitain esimerkkejä Java-kielellä, ja ne ovat riittävän yksinkertaisia, jotta kuka tahansa, jolla on jonkin verran ohjelmointikokemusta, voi tulkita ne.

Mikä on rekursio?

Rekursio ymmärretään ottamalla askel taaksepäin ohjelmoinnista. Aloitetaan luomalla termille yleinen määritelmä. Jotain on rekursiivista, jos se määritellään jossain määrin sen omalla määritelmällä. Se ei todennäköisesti auta sinua ymmärtämään rekursiota kovin paljon, joten katsotaanpa matemaattinen määritelmä. Olet perehtynyt toimintoihin - yksi numero tulee sisään, toinen numero tulee ulos. Ne näyttävät tältä:

f (x) = 2x

Muutetaan tätä ajatusta hieman ja pohditaan sen sijaan sarjaa. Sarja ottaa kokonaisluvun, ja kokonaisluku tulee ulos.

A (n) = 2n

Sekvenssit voidaan ajatella toiminnoiksi, joissa on sisääntulot ja lähdöt, jotka rajoittuvat vain positiivisiin kokonaislukuihin. Yleensä sekvenssit alkavat 1. Tämä tarkoittaa, että A (0) on 1. Yllä oleva sekvenssi on seuraava:

A (n) = 1, 2, 4, 6, 8, 10,… missä n = 0, 1, 2, 3, 4, 5,…

Harkitse nyt seuraavaa järjestystä:

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

Tämä sekvenssi määritetään rekursiivisesti. Toisin sanoen minkä tahansa elementin arvo riippuu toisen elementin arvosta. Tämä jakso näyttää tältä:

A (n) = 1, 2, 4, 8, 16,… missä n = 0, 1, 2, 3, 4,…

Mikä tahansa elementti määritellään 2 kertaa edelliselle elementille.

  • N = 4 elementti, 16, määritellään 2 kertaa edellinen elementti.
  • Elementti n = 3, 8, määritellään 2 kertaa edellinen elementti.
  • Elementti n = 2, 4, määritellään 2 kertaa edellinen elementti.
  • N = 1 elementti, 2, määritellään 2 kertaa edellinen elementti.
  • Elementti n = 0, 1, määritellään seuraavasti:

Elementtiä n = 0 ei voida määrittää rekursiivisesti. Edellistä elementtiä ei ole. Kutsumme tätä perustapaukseksi , ja se on rekursiivisten määritelmien välttämätön seuraus. Niiden on oltava nimenomaisesti edustettuina koodissasi . Voisimme edustaa tätä rekursiivista sekvenssiä Java-muodossa näin:

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

Sinun tulisi tutustua rekursiivisen menetelmän anatomiaan. Huomaa perustapaus: jos n on 0, elementti määritetään 1. Muussa tapauksessa elementti määritellään 2 kertaa edellinen elementti. Meidän on rekursiivisesti kutsuttava menetelmää saadaksesi edellisen elementin arvo ja kerrottava se sitten kahdella. Kaikilla rekursiivisilla menetelmillä on nämä kaksi komponenttia:

  • Perustapaus, joka palauttaa hyvin määritellyn arvon.
  • Rekursiivinen tapaus, joka palauttaa rekursiivisesti määritetyn arvon.

Tehdään toinen esimerkki jatkamalla matematiikan kontekstia. Fibonacci-sekvenssiä käytetään usein kuvaamaan rekursiota. Mikä tahansa Fibonacci-sekvenssin elementti on kahden edellisen elementin summa. Se menee näin:

F (n) = 1, 1, 2, 3, 5, 8,… missä n = 0, 1, 2, 3, 4, 5,…

  • Elementti n = 5, elementti 8, määritetään n = 4 -elementin ja n = 3 -elementin summana…

Tässä vaiheessa sinun pitäisi epäröidä. Edellisessä esimerkissä kukin elementti riippui vain yhdestä muusta elementistä, nyt kukin elementti riippuu kahdesta muusta elementistä. Tämä vaikeuttaa asioita.

  • Elementti n = 4, 5, määritellään n = 3 -elementin ja n = 2 -elementin summana.
  • Elementti n = 3, 3, määritellään n = 2-elementin ja n = 1 -elementin summana.
  • Elementti n = 2, 2, määritellään n = 1 -elementin ja n = 0 -elementin summana.
  • Elementti n = 1, 1, määritellään n = 0 -elementin ja…

Elementtiä n = 1 ei voida määrittää rekursiivisesti. Myöskään n = 0 -elementti ei voi. Näitä elementtejä ei voida määrittää rekursiivisesti, koska rekursiivinen määritelmä vaatii kaksi edeltävää elementtiä. Elementillä n = 0 ei ole edeltäviä elementtejä, ja n = 1 -elementillä on vain yksi edeltävä elementti. Tämä tarkoittaa, että on olemassa kaksi perustapausta. Ennen koodin kirjoittamista kirjoitin muistiin jotain tällaista:

Elementti n = 0 on määritelty 1. Elementti n = 1 on määritelty 1: ksi.

N-elementti määritellään n-1-elementin ja n-2-elementin summana.

Nyt meillä on käsitys siitä, miten tämä tehtävä määritetään rekursiivisesti, ja voimme mennä eteenpäin ja kirjoittaa koodin. Ei koskaanaloita koodin kirjoittaminen ilman, että ensin ymmärrät luonnostaan ​​tehtävää.

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

Puhelupino

Ohjelmoijina haluamme saada intuition rekursiosta, jotta voimme käyttää sitä asioiden tekemiseen. Tehdäkseen tämän tehokkaasti meidän on ymmärrettävä, kuinka tietokone käsittelee rekursiota.

On olemassa tietorakenne, jota tietokone käyttää seuraamaan menetelmäpuheluja, joita kutsutaan puhelupinoksi . Jokainen menetelmäpuhelu luo paikalliset muuttujat menetelmäparametreista. Tietokoneen on tallennettava nämä muuttujat menetelmän suorituksen aikana. Sitten tietokone ojentaa arvot, kun menetelmä palaa, jotta vältetään muistin tuhlaaminen.

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?”

Muista, että yritimme korvata menetelmän, joka käytti a for -silmukkaa. Tuo menetelmä oli yksinkertainen. Se otti matriisin parametrina ja palautti matriisin summan kaksinkertaisena. Jos korvaamme tämän menetelmän kolmella parametrilla, meidän on muistettava kutsua sitä oikeilla lähtöarvoilla. Jos joku muu haluaa käyttää menetelmääsi, olisi mahdotonta, jos hän ei tiedä lähtöarvoja.

Näistä syistä on järkevää lisätä toinen menetelmä, joka huolehtii näistä lähtöarvoista meille.

Käärimistä

Rekursio on melko haastava käsite, mutta teit sen selitykseni loppuun asti. Toivon, että ymmärrät taikaa hieman paremmin. Myönnän sinulle nyt virallisesti ”Grand Wizard of Recursion” -tittelin. Onnittelut!