Rekursio on tietojenkäsittelytieteen ja matematiikan peruskäsite, jonka avulla funktiot voivat kutsua itseään, mikä mahdollistaa monimutkaisten ongelmien ratkaisemisen iteratiivisten vaiheiden kautta. Yksi visuaalinen esitys, jota yleisesti käytetään ymmärtämään ja analysoimaan rekursiivisten funktioiden suorittamista, on rekursiopuu. Tässä artikkelissa tutkimme rekursiopuiden taustalla olevaa teoriaa, niiden rakennetta ja merkitystä rekursiivisten algoritmien ymmärtämisessä.

Mikä on rekursiopuu?

Rekursiopuu on graafinen esitys, joka havainnollistaa rekursiivisen funktion suorituskulkua. Se tarjoaa visuaalisen erittelyn rekursiivisista puheluista ja esittelee algoritmin etenemisen sen haarautuessa ja lopulta saavuttaessa perustapauksen. Puurakenne auttaa analysoimaan ajan monimutkaisuutta ja ymmärtämään siihen liittyvää rekursiivista prosessia.

Puun rakenne

Jokainen solmu rekursiopuussa edustaa tiettyä rekursiivista kutsua. Ensimmäinen puhelu on kuvattu yläosassa, ja seuraavat puhelut haarautuvat sen alla. Puu kasvaa alaspäin muodostaen hierarkkisen rakenteen. Kunkin solmun haarautumiskerroin riippuu funktion sisällä tehtyjen rekursiivisten kutsujen määrästä. Lisäksi puun syvyys vastaa rekursiivisten kutsujen määrää ennen perustapauksen saavuttamista.

Perustapaus

Perustapaus toimii rekursiivisen funktion lopetusehtona. Se määrittää pisteen, jossa rekursio pysähtyy ja funktio alkaa palauttaa arvoja. Rekursiopuussa perustapausta edustavat solmut on yleensä kuvattu lehtisolmuina, koska ne eivät johda uusiin rekursiivisiin kutsuihin.

Rekursiiviset puhelut

Rekursiopuun lapsisolmut edustavat funktion sisällä tehtyjä rekursiivisia kutsuja. Jokainen lapsisolmu vastaa erillistä rekursiivista kutsua, mikä johtaa uusien aliongelmien luomiseen. Näille rekursiivisille kutsuille välitetyt arvot tai parametrit voivat vaihdella, mikä johtaa vaihteluihin aliongelmien ominaisuuksissa.

Toteutuskulku:

Rekursiopuun läpi kulkeminen antaa käsityksen rekursiivisen funktion suorituskulusta. Aloituskutsusta juurisolmussa seuraamme haaroja päästäksemme seuraaviin kutsuihin, kunnes kohtaamme perustapauksen. Kun perustapaukset saavutetaan, rekursiiviset kutsut alkavat palata ja niiden vastaavat solmut puussa merkitään palautetuilla arvoilla. Kulkua jatketaan, kunnes koko puu on ajettu.

Aika monimutkaisuusanalyysi

Rekursiopuut auttavat analysoimaan rekursiivisten algoritmien aikamonimutkaisuutta. Puun rakennetta tarkastelemalla voimme määrittää kullekin tasolle tehtyjen rekursiivisten kutsujen määrän ja tehdyn työn. Tämä analyysi auttaa ymmärtämään algoritmin kokonaistehokkuutta ja tunnistamaan mahdolliset tehottomuudet tai optimointimahdollisuudet.

10 prosenttia 60:stä

Johdanto

• Ajattele ohjelmaa, joka määrittää luvun kertoimen. Tämä funktio ottaa luvun N syötteeksi ja palauttaa tuloksena N:n kertoimen. Tämän toiminnon pseudokoodi muistuttaa

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Rekursiosta on esimerkkinä aiemmin mainittu toiminto. Käytämme funktiota luvun kertoimen määrittämiseksi. Sitten tämä funktio kutsuu itseään, jos samalle numerolle on annettu pienempi arvo. Tätä jatketaan, kunnes saavutetaan perustapaus, jossa ei ole enää funktiokutsuja.
• Rekursio on tekniikka monimutkaisten ongelmien käsittelyyn, kun tulos riippuu saman ongelman pienempien tapausten tuloksista.
• Jos ajattelemme funktioita, funktion sanotaan olevan rekursiivinen, jos se kutsuu itseään, kunnes se saavuttaa perustapauksen.
• Jokaisella rekursiivisella funktiolla on kaksi pääkomponenttia: perustapaus ja rekursiivinen askel. Lopetamme menemisen rekursiiviseen vaiheeseen, kun saavutamme perustapauksen. Loputtoman toistumisen estämiseksi perustapaukset on määriteltävä oikein ja ne ovat tärkeitä. Äärettömän rekursion määritelmä on rekursio, joka ei koskaan saavuta perustapausta. Jos ohjelma ei koskaan saavuta perustapausta, pinon ylivuoto jatkuu.

Rekursiotyypit

Yleisesti ottaen on olemassa kaksi erilaista rekursiomuotoa:

• Lineaarinen rekursio
• Puun rekursio
• Lineaarinen rekursio

Lineaarinen rekursio

• Funktiota, joka kutsuu itseään vain kerran joka kerta kun se suoritetaan, sanotaan olevan lineaarisesti rekursiivinen. Hieno esimerkki lineaarisesta rekursiosta on tekijäfunktio. Nimi 'lineaarinen rekursio' viittaa siihen, että lineaarisesti rekursiivisen funktion suorittaminen vie lineaarisesti aikaa.
• Katso alla olevaa pseudokoodia:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Jos katsomme funktiota doSomething(n), se hyväksyy parametrin nimeltä n ja tekee joitain laskutoimituksia ennen kuin kutsuu saman proseduurin vielä kerran, mutta pienemmillä arvoilla.
• Kun menetelmää doSomething() kutsutaan argumentin arvolla n, oletetaan, että T(n) edustaa laskennan suorittamiseen tarvittavaa kokonaisaikaa. Tätä varten voidaan myös muotoilla toistuvuusrelaatio, T(n) = T(n-1) + K. K toimii tässä vakiona. Vakio K on mukana, koska funktiolta kuluu aikaa varata tai purkaa muistia muuttujalle tai suorittaa matemaattinen operaatio. Käytämme K-kirjainta ajan määrittämiseen, koska se on niin pieni ja merkityksetön.
• Tämän rekursiivisen ohjelman aikamonimutkaisuus voidaan yksinkertaisesti laskea, koska pahimmassa tapauksessa menetelmää doSomething() kutsutaan n kertaa. Muodollisesti funktion ajallinen monimutkaisuus on O(N).

Puun rekursio

• Kun teet rekursiivisen kutsun rekursiivisessa tapauksessasi useammin kuin kerran, sitä kutsutaan puurekursioksi. Tehokas esimerkki puun rekursiosta on fibonacci-sekvenssi. Puun rekursiiviset funktiot toimivat eksponentiaalisessa ajassa; ne eivät ole lineaarisia ajallisessa monimutkaisuudessaan.
• Katso alla olevaa pseudokoodia,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Ainoa ero tämän koodin ja edellisen välillä on, että tämä soittaa vielä yhden kutsun samalle funktiolle pienemmällä arvolla n.
• Laitetaan T(n) = T(n-1) + T(n-2) + k tämän funktion toistuvuusrelaatioksi. K toimii jälleen vakiona.
• Kun samalle funktiolle suoritetaan useampi kuin yksi kutsu pienemmillä arvoilla, tällaista rekursiota kutsutaan puurekursioksi. Kiinnostava näkökohta on nyt: kuinka aikaa vievä tämä toiminto on?
• Tee arvaus alla olevan rekursiopuun perusteella samasta funktiosta.
  
• Sinulle saattaa tulla mieleen, että on haastavaa arvioida ajan monimutkaisuutta katsomalla suoraan rekursiivista funktiota, varsinkin kun se on puurekursio. Rekursiopuumenetelmä on yksi useista tekniikoista tällaisten funktioiden ajallisen monimutkaisuuden laskemiseksi. Tarkastellaanpa sitä tarkemmin.

Mikä on rekursiopuumenetelmä?

• Toistuvuusrelaatiot, kuten T(N) = T(N/2) + N tai ne kaksi, joita käsittelimme aiemmin erityyppisissä rekursioosiossa, ratkaistaan ​​käyttämällä rekursiopuun lähestymistapaa. Näissä toistuvissa suhteissa käytetään usein hajota ja hallitse -strategiaa ongelmien ratkaisemiseen.
• Kestää aikaa integroida vastaukset pienempiin osaongelmiin, jotka syntyvät, kun suurempi ongelma jaetaan pienempiin osaongelmiin.
• Toistuvuussuhde on esimerkiksi T(N) = 2 * T(N/2) + O(N) yhdistämislajittelulle. Aika, joka tarvitaan vastausten yhdistämiseen kahteen osatehtävään, joiden yhteiskoko on T(N/2), on O(N), mikä pätee myös toteutustasolla.
• Esimerkiksi, koska binäärihaun toistuvuussuhde on T(N) = T(N/2) + 1, tiedämme, että jokainen binäärihaun iteraatio johtaa hakuavaruuteen, joka leikataan puoliksi. Kun tulos on määritetty, poistumme funktiosta. Toistuvuusrelaatioon on lisätty +1, koska tämä on vakioaikatoiminto.
• Toistuvuussuhde T(n) = 2T(n/2) + Kn on otettava huomioon. Kn tarkoittaa aikaa, joka tarvitaan n/2-ulotteisten osatehtävien vastausten yhdistämiseen.
• Kuvataan rekursiopuu edellä mainitulle toistuvuusrelaatiolle.

Voimme tehdä muutamia johtopäätöksiä tutkimalla yllä olevaa rekursiopuuta, mukaan lukien

1. Ongelman suuruus kullakin tasolla on ratkaiseva tekijä solmun arvon määrittämisessä. Julkaisun koko on n tasolla 0, n/2 tasolla 1, n/2 tasolla 2 ja niin edelleen.

2. Yleensä määrittelemme puun korkeuden yhtä suureksi kuin log (n), jossa n on ongelman koko ja tämän rekursiopuun korkeus on yhtä suuri kuin puun tasojen lukumäärä. Tämä on totta, koska kuten juuri totesimme, toistuvuussuhteet käyttävät hajota ja hallitse -strategiaa ongelmien ratkaisemiseen, ja ongelman koosta n päästäminen ongelman kokoon 1 vaatii yksinkertaisesti log (n) askelten ottamista.

• Tarkastellaan esimerkiksi arvoa N = 16. Jos saamme jakaa N 2:lla kussakin vaiheessa, kuinka monta askelta tarvitaan saadakseen N = 1? Kun otetaan huomioon, että jaamme kahdella jokaisessa vaiheessa, oikea vastaus on 4, joka on log(16) kantaluvun 2 arvo.

log(16) kanta 2

log(2^4) kanta 2

4 * log(2) kantaluku 2, koska log(a) kanta a = 1

siis 4 * log(2) kantaluku 2 = 4

3. Jokaisella tasolla toistumisen toista termiä pidetään juurena.

Vaikka sana 'puu' esiintyy tämän strategian nimessä, sinun ei tarvitse olla puiden asiantuntija ymmärtääksesi sen.

Kuinka käyttää rekursiopuuta toistumissuhteiden ratkaisemiseen?

Osaongelman hinta rekursiopuutekniikassa on aika, joka tarvitaan osatehtävän ratkaisemiseen. Siksi, jos huomaat lauseen 'kustannus', joka on linkitetty rekursiopuuhun, se tarkoittaa yksinkertaisesti aikaa, joka tarvitaan tietyn aliongelman ratkaisemiseen.

Ymmärretään kaikki nämä vaiheet muutaman esimerkin avulla.

Esimerkki

Harkitse toistumissuhdetta,

T(n) = 2T(n/2) + K

Ratkaisu

Annettu toistuvuussuhde näyttää seuraavat ominaisuudet,

Ongelman koko n on jaettu kahteen osaongelmaan, joista kumpikin on kokoa n/2. Näiden osaongelmien ratkaisujen yhdistämisen hinta on K.

Jokainen tehtäväkoko n/2 on jaettu kahteen osaongelmaan, joista kumpikin on kokoa n/4 ja niin edelleen.

Viimeisellä tasolla aliongelman koko pienennetään 1:een. Toisin sanoen, lopulta osuimme perustapaukseen.

Noudatetaan vaiheita tämän toistumissuhteen ratkaisemiseksi,

Vaihe 1: Piirrä rekursiopuu

Vaihe 2: Laske puun korkeus

Koska tiedämme, että kun jaamme luvun jatkuvasti kahdella, tulee aika, jolloin tämä luku pienenee 1:ksi. Sama kuin ongelman koossa N, oletetaan K:n jakamisen jälkeen 2:lla N tulee yhtä suureksi kuin 1, mikä tarkoittaa, ( n/2^k) = 1

Tässä n / 2^k on ongelman koko viimeisellä tasolla ja se on aina yhtä suuri kuin 1.

Nyt voimme helposti laskea k:n arvon yllä olevasta lausekkeesta ottamalla log() molemmille puolille. Alla on selkeämpi johtopäätös,

n = 2^k

elokuvanäyttelijä Kajal

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) kantaluku 2

Joten puun korkeus on log (n) kanta 2.

Vaihe 3: Laske kustannukset kullakin tasolla

• Kustannukset tasolla-0 = K, kaksi aliongelmaa yhdistetään.
• Kustannukset tasolla-1 = K + K = 2*K, kaksi aliongelmaa yhdistetään kahdesti.
• Kustannukset tasolla-2 = K + K + K + K = 4*K, kaksi alitehtävää yhdistetään neljä kertaa. ja niin edelleen....

Vaihe 4: Laske solmujen lukumäärä kullakin tasolla

Määritetään ensin solmujen lukumäärä viimeisellä tasolla. Rekursiopuusta voimme päätellä tämän

• Tasolla 0 on 1 (2^0) solmu
• Tasolla 1 on 2 (2^1) solmua
• Tasolla 2 on 4 (2^2) solmua
• Tasolla 3 on 8 (2^3) solmua

Tason log(n) pitäisi siis sisältää 2^(log(n)) solmua eli n solmua.

Vaihe 5: Tee yhteenveto kaikkien tasojen kustannuksista

• Kokonaiskustannukset voidaan kirjoittaa seuraavasti:
• Kokonaiskustannukset = kaikkien tasojen kustannukset paitsi viimeinen taso + viimeisen tason kustannukset
• Kokonaiskustannukset = Kustannukset tasolle-0 + Kustannukset tasolle-1 + Kustannukset tasolle-2 +.... + Kustannukset tasolle-log(n) + Kustannukset viimeiselle tasolle

Viimeisen tason hinta lasketaan erikseen, koska se on perustapaus ja viimeisellä tasolla ei tehdä yhdistämistä, joten yksittäisen ongelman ratkaiseminen tällä tasolla on jokin vakioarvo. Otetaan se muotoon O (1).

Laitetaan arvot kaavoihin,

• T(n) = K + 2*K + 4*K + .... + log(n) kertaa + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) kertaa)' + 'O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) kertaa + O(n)

Jos tarkastelet yllä olevaa lauseketta tarkasti, se muodostaa geometrisen etenemisen (a, ar, ar^2, ar^3 ...... ääretön aika). GP:n summa saadaan kaavalla S(N) = a / (r - 1). Tässä on ensimmäinen termi ja r on yhteinen suhde.