Põhierinevus – rekursioon vs iteratsioon
Rekursiooni ja iteratsiooni saab kasutada programmeerimisprobleemide lahendamiseks. Probleemi lahendamise viis rekursiooni või iteratsiooni abil sõltub probleemi lahendamise viisist. Peamine erinevus rekursiooni ja iteratsiooni vahel on see, et rekursioon on mehhanism funktsiooni kutsumiseks samas funktsioonis, samas kui iteratsioon on käskude komplekti korduv alt täitmine, kuni antud tingimus on tõene. Rekursioon ja iteratsioon on peamised meetodid algoritmide arendamiseks ja tarkvararakenduste loomiseks.
Mis on rekursioon?
Kui funktsioon kutsub end funktsiooni sees välja, nimetatakse seda rekursiooniks. Rekursiooni on kahte tüüpi. Need on piiratud rekursioon ja lõpmatu rekursioon. Piiratud rekursioonil on lõpptingimus. Lõpmatul rekursioonil pole lõpptingimust.
Rekursiooni saab seletada faktoriaalide arvutamise programmi abil.
n!=n(n-1)!, kui n>0
n!=1, kui n=0;
Vaadake allolevat koodi, et arvutada faktoriaal 3(3!=321).
intmain () {
int väärtus=faktoriaalne (3);
printf("Tegur on %d\n", väärtus);
tagasi 0;
}
infactorial (intn) {
if(n==0) {
tagasi 1;
}
muu {
tagasi n faktoriaal(n-1);
}
}
Faktooriumi (3) kutsumisel kutsub see funktsioon esile faktoriaali (2). Faktoriaali (2) kutsumisel kutsub see funktsioon esile faktoriaali (1). Seejärel kutsub faktoriaal (1) faktoriaali (0). faktoriaal (0) tagastab 1. Ül altoodud programmis on n==0 tingimus „kui plokis” põhitingimus. Vastav alt Samamoodi kutsutakse faktoriaalfunktsiooni ikka ja jälle.
Rekursiivsed funktsioonid on seotud virnaga. C-s võib põhiprogrammil olla palju funktsioone. Niisiis, main () on kutsuv funktsioon ja funktsioon, mida põhiprogramm kutsub, on kutsutud funktsioon. Funktsiooni kutsumisel antakse juhtimine kutsutavale funktsioonile. Pärast funktsiooni täitmise lõpetamist naaseb juhtseade põhirežiimile. Seejärel jätkub põhiprogramm. Seega loob see käivitamise jätkamiseks aktiveerimiskirje või virnaraami.
Joonis 01: Rekursioon
Ül altoodud programmis, kui helistate faktoriaalile (3) põhivõrgust, loob see kõnepinusse aktiveerimiskirje. Seejärel luuakse virna peale faktoriaalne (2) virnaraam ja nii edasi. Aktiveerimiskirje hoiab teavet kohalike muutujate jms kohta. Iga kord, kui funktsiooni kutsutakse, luuakse virna ülaossa uus kohalike muutujate komplekt. Need virnaraamid võivad kiirust aeglustada. Sarnaselt rekursiooniga kutsub funktsioon ise välja. Rekursiivse funktsiooni ajaline keerukus leitakse funktsiooni kutsumise kordade arvu järgi. Ühe funktsioonikutse ajaline keerukus on O(1). N arvu rekursiivsete kõnede korral on ajaline keerukus O(n).
Mis on iteratsioon?
Iteratsioon on käskude plokk, mis kordub ikka ja jälle, kuni antud tingimus on tõene. Iteratsiooni saab saavutada kasutades "for loop", "do-while loop" või "while loop". "For loop" süntaks on järgmine.
for (initsialiseerimine; tingimus; muutmine) {
// avaldused;
}
Joonis 02: "tsükli vooskeem"
Initsialiseerimise samm käivitatakse esimesena. See samm on tsükli juhtmuutujate deklareerimine ja lähtestamine. Kui tingimus on tõene, täidetakse lokkis sulgudes olevad laused. Neid väiteid täidetakse seni, kuni tingimus on tõene. Kui tingimus on väär, liigub juhtelement järgmise lause juurde pärast tsüklit "for silmus". Pärast tsükli sees olevate lausete täitmist läheb juhtelement jaotisse muutmine. See on silmuse juhtmuutuja värskendamine. Seejärel kontrollitakse seisukorda uuesti. Kui tingimus on tõene, täidetakse lokkis sulgudes olevad laused. Nii itereerub "for tsükkel".
Keskuses "while loop" käivitatakse tsükli sees olevad laused, kuni tingimus on tõene.
while (seisukord){
//avaldused
}
Singluses "do-while" kontrollitakse tingimust tsükli lõpus. Seega käivitatakse tsükkel vähem alt korra.
teha{
//avaldused
} while(seisund)
Programm 3 (3!) faktoriaali leidmiseks, kasutades iteratsiooni (“silmus”), on järgmine.
int main(){
intn=3, faktoriaal=1;
inti;
for(i=1; i<=n; i++){
faktoriaal=faktoriaali;
}
printf("Faktsiaal on %d\n", faktoriaal);
tagasi 0;
}
Millised on rekursiooni ja iteratsiooni sarnasused?
- Mõlemad on tehnikad probleemi lahendamiseks.
- Ülesannet saab lahendada kas rekursiooni või iteratsiooni teel.
Mis vahe on rekursioonil ja iteratsioonil?
Rekursioon vs iteratsioon |
|
| Rekursioon on meetod funktsiooni kutsumiseks samas funktsioonis. | Iteratsioon on käskude plokk, mis kordub, kuni antud tingimus on tõene. |
| Ruumi keerukus | |
| Rekursiivsete programmide ruumiline keerukus on suurem kui iteratsioonidel. | Ruumi keerukus on iteratsioonides väiksem. |
| Kiirus | |
| Rekursiooni täitmine on aeglane. | Tavaliselt on iteratsioon kiirem kui rekursioon. |
| Seisukord | |
| Kui lõpetamise tingimust pole, võib esineda lõpmatu rekursioon. | Kui tingimus ei muutu kunagi vääraks, on see lõpmatu iteratsioon. |
| Virna | |
| Rekursioonis kasutatakse virna funktsiooni kutsumisel kohalike muutujate salvestamiseks. | Iteratsioonis pinu ei kasutata. |
| Koodi loetavus | |
| Rekursiivne programm on loetavam. | Iteratiivset programmi on raskem lugeda kui rekursiivset programmi. |
Kokkuvõte – rekursioon vs iteratsioon
Selles artiklis käsitleti erinevust rekursiooni ja iteratsiooni vahel. Mõlemat saab kasutada programmeerimisprobleemide lahendamiseks. Erinevus rekursiooni ja iteratsiooni vahel seisneb selles, et rekursioon on mehhanism sama funktsiooni sees oleva funktsiooni väljakutsumiseks ja selle itereerimiseks käskude komplekti korduv alt täitmiseks, kuni antud tingimus on tõene. Kui probleemi saab lahendada rekursiivsel kujul, saab seda lahendada ka iteratsioonide abil.
Laadige alla rekursiooni ja iteratsiooni PDF-versioon
Saate alla laadida selle artikli PDF-versiooni ja kasutada seda võrguühenduseta kasutamiseks vastav alt tsitaadi märkusele. Laadige PDF-versioon alla siit. Erinevus rekursiooni ja iteratsiooni vahel
