Avainero – Rekursio vs iteraatio
Rekursiota ja iteraatiota voidaan käyttää ohjelmointiongelmien ratkaisemiseen. Ongelman ratkaisutapa rekursion tai iteroinnin avulla riippuu ongelman ratkaisutavasta. Keskeinen ero rekursion ja iteraation välillä on se, että rekursio on mekanismi funktion kutsumiseksi saman funktion sisällä, kun taas iteraatio on suorittaa joukko käskyjä toistuvasti, kunnes annettu ehto on tosi. Rekursio ja iteraatio ovat tärkeitä tekniikoita algoritmien kehittämiseen ja ohjelmistosovellusten rakentamiseen.
Mikä on rekursio?
Kun funktio kutsuu itseään funktiossa, sitä kutsutaan rekursioksi. Rekursiota on kahta tyyppiä. Ne ovat äärellinen rekursio ja ääretön rekursio. Äärillisellä rekursiolla on loppuehto. Äärettömällä rekursiolla ei ole pääteehtoa.
Rekursio voidaan selittää ohjelman avulla tekijälukujen laskemiseen.
n!=n(n-1)!, jos n>0
n!=1, jos n=0;
Katso alla olevaa koodia laskeaksesi kertoimen 3(3!=321).
intmain () {
int arvo=tekijä (3);
printf("Facterial on %d\n", arvo);
palautus 0;
}
infactorial (intn) {
if(n==0) {
palautus 1;
}
muuta {
return n factorial(n-1);
}
}
Kutsuttaessa factorial (3), tämä toiminto kutsuu factorial (2). Kutsuttaessa factorial (2), tämä funktio kutsuu factorial (1). Sitten faktoriaali (1) kutsuu faktoriaalia (0). factorial (0) palauttaa arvon 1. Yllä olevassa ohjelmassa n==0 ehto "jos-lohkossa" on perusehto. Samoin mukaan tekijäfunktiota kutsutaan yhä uudelleen.
Rekursiiviset funktiot liittyvät pinoon. C:ssä pääohjelmalla voi olla monia toimintoja. Joten main () on kutsuva funktio, ja funktio, jota pääohjelma kutsuu, on kutsuttu funktio. Kun funktiota kutsutaan, ohjataan kutsutulle funktiolle. Kun toiminto on suoritettu, ohjaus palautetaan päätilaan. Sen jälkeen pääohjelma jatkuu. Joten se luo aktivointitietueen tai pinokehyksen suorituksen jatkamista varten.
Kuva 01: Rekursio
Yllä olevassa ohjelmassa se luo aktivointitietueen puhelupinoon kutsuttaessa faktorialia (3) mainista. Sitten pinon päälle luodaan faktoriaalinen (2) pinokehys ja niin edelleen. Aktivointitietue säilyttää tiedot paikallisista muuttujista jne. Joka kerta kun funktiota kutsutaan, pinon päälle luodaan uusi joukko paikallisia muuttujia. Nämä pinokehykset voivat hidastaa nopeutta. Samoin rekursiossa funktio kutsuu itseään. Rekursiivisen funktion aikamonimutkaisuus määritetään sen mukaan, kuinka monta kertaa funktiota kutsutaan. Aika monimutkaisuus yhdelle funktiokutsulle on O(1). N määrälle rekursiivisia kutsuja aikamonimutkaisuus on O(n).
Mitä iteraatio on?
Iteraatio on komentolohko, joka toistuu uudestaan ja uudestaan, kunnes annettu ehto on tosi. Iterointi voidaan saavuttaa käyttämällä "for loop", "do-while loop" tai "while loop". "for loop" -syntaksi on seuraava.
for (alustus; kunto; muokkaa) {
// lausunnot;
}
Kuva 02: "silmukan vuokaavio"
Alustusvaihe suoritetaan ensin. Tämä vaihe on silmukan ohjausmuuttujien ilmoittaminen ja alustaminen. Jos ehto on tosi, a altosulkeiden sisällä olevat lauseet suoritetaan. Nämä lausunnot toteutuvat, kunnes ehto on tosi. Jos ehto on epätosi, ohjaus siirtyy seuraavaan lauseeseen "for-silmukan" jälkeen. Kun käskyt on suoritettu silmukan sisällä, ohjaus siirtyy muokkaa-osaan. Se on silmukan ohjausmuuttujan päivittäminen. Sitten kunto tarkistetaan uudelleen. Jos ehto on tosi, a altosulkeiden sisällä olevat lauseet suoritetaan. Tällä tavalla "for-silmukka" iteroituu.
While-silmukassa silmukan sisällä olevat lauseet suoritetaan, kunnes ehto on tosi.
while (kunto){
//lausunnot
}
Do-while-silmukassa ehto tarkistetaan silmukan lopussa. Joten silmukka suoritetaan vähintään kerran.
tee{
//lausunnot
} while(ehto)
Ohjelma 3:n (3!) kertoimen löytämiseksi iteraatiolla ("for loop") on seuraava.
int main(){
intn=3, tekijä=1;
inti;
for(i=1; i<=n; i++){
factorial=factoriali;
}
printf("Factoriaal on %d\n", factorial);
palautus 0;
}
Mitä yhtäläisyyksiä rekursiolla ja iteraatiolla on?
- Molemmat ovat tekniikoita ongelman ratkaisemiseksi.
- Tehtävä voidaan ratkaista joko rekursiolla tai iteraatiolla.
Mitä eroa on rekursiolla ja iteraatiolla?
Rekursio vs iteraatio |
|
| Rekursio on menetelmä kutsua funktio saman funktion sisällä. | Iteraatio on komentolohko, joka toistuu, kunnes annettu ehto on tosi. |
| Avaruuden monimutkaisuus | |
| Rekursiivisten ohjelmien monimutkaisuus on suurempi kuin iteraatioiden. | Avaruuden monimutkaisuus on pienempi iteraatioissa. |
| Nopeus | |
| Rekursion suoritus on hidasta. | Tavallisesti iteraatio on nopeampaa kuin rekursio. |
| Kunto | |
| Jos lopetusehtoa ei ole, rekursio voi olla ääretön. | Jos ehdosta ei koskaan tule epätosi, se on loputon iteraatio. |
| Pino | |
| Rekursiossa pinoa käytetään paikallisten muuttujien tallentamiseen, kun funktiota kutsutaan. | Iteraatiossa pinoa ei käytetä. |
| Koodin luettavuus | |
| Rekursiivinen ohjelma on luettavampi. | Iteratiivista ohjelmaa on vaikeampi lukea kuin rekursiivista ohjelmaa. |
Yhteenveto – Rekursio vs iteraatio
Tässä artikkelissa käsiteltiin eroa rekursion ja iteraation välillä. Molempia voidaan käyttää ohjelmointiongelmien ratkaisemiseen. Ero rekursion ja iteraation välillä on se, että rekursio on mekanismi, joka kutsuu funktiota saman funktion sisällä ja iteroi sitä käskyjen suorittamiseksi toistuvasti, kunnes annettu ehto on tosi. Jos ongelma voidaan ratkaista rekursiivisessa muodossa, se voidaan ratkaista myös iteraatioiden avulla.
Lataa Recursion vs Iteration PDF-versio
Voit ladata tämän artikkelin PDF-version ja käyttää sitä offline-tarkoituksiin lainaushuomautuksen mukaisesti. Lataa PDF-versio tästä Rekursion ja iteroinnin ero
