Razlika med rekurzijo in iteracijo

Ključna razlika - rekurzija vs ponovitev
 

Za reševanje težav s programiranjem se lahko uporabljata rekurzija in iteracija. Pristop k reševanju problema s pomočjo rekurzije ali iteracije je odvisen od načina reševanja problema. The ključna razlika med rekurzijo in iteracijo je to rekurzija je mehanizem za klic funkcije znotraj iste funkcije, medtem ko je iteracija večkrat izvajati nabor navodil, dokler ni podan pogoj. Rekurzija in iteracija sta glavni tehniki za razvoj algoritmov in gradnjo programskih aplikacij.

VSEBINA

1. Pregled in ključne razlike
2. Kaj je rekurzija
3. Kaj je iteracija
4. Podobnosti rekurzije in iteracije
5. Primerjava ob strani - rekurzija proti ponovitvi v tabeli
6. Povzetek

Kaj je rekurzija?

Ko se funkcija pokliče znotraj funkcije, je znana kot rekurzija. Obstajata dve vrsti rekurzije. So končna rekurzija in neskončna rekurzija. Končna rekurzija ima prenehanje stanja. Neskončna rekurzija nima prenehanja pogoja.

Rekurzijo je mogoče razložiti s programom za izračun tovarn.

n! = n * (n-1) !, če je n> 0

n! = 1, če je n = 0;

Glej spodnjo kodo za izračun faktorja 3 (3! = 3 * 2 * 1).

intmain ()

int vrednost = faktorski (3);

printf (vrednost »Faktororial je% d \ n«);

vrne 0;

intfactorial (intn)

če (n == 0)

vrnitev 1;

drugače

vrne n * faktororial (n-1);

Ko pokličete faktororial (3), bo ta funkcija poklicala faktororial (2). Ko pokličete faktororial (2), bo ta funkcija poklicala faktororial (1). Potem bo faktororial (1) poklical faktororial (0). faktororial (0) se vrne 1. V zgornjem programu je osnovni pogoj n == 0 v "če je blok". Po podobnem se faktoristična funkcija imenuje vedno znova.

Rekurzivne funkcije so povezane s skladom. V C ima lahko glavni program veliko funkcij. Torej, main () je klicna funkcija, funkcija, ki jo pokliče glavni program, pa je imenovana funkcija. Ko se pokliče funkcija, se nadzor podeli klicani funkciji. Ko je izvedba funkcije končana, se nadzor vrne v glavni. Nato se nadaljuje glavni program. Torej ustvari aktivacijski zapis ali sklad skladbe za nadaljevanje izvajanja.

Slika 01: Rekurzija

V zgornjem programu, ko pokličete faktororial (3) z glavnega, ustvari aktivacijski zapis v zbirki klicev. Nato se ustvari okvir zložen faktororial (2) na vrhu in podobno. V aktivacijskem zapisu so shranjene informacije o lokalnih spremenljivkah itd. Vsakič, ko je funkcija poklicana, se na vrhu zložbe ustvari nov niz lokalnih spremenljivk. Ti okviri skladov lahko upočasnijo hitrost. Prav tako v rekurziji se funkcija pokliče sama. Časovno kompleksnost rekurzivne funkcije najdemo po številu krat, kliče se funkcija. Časovna zapletenost za en funkcijski klic je O (1). Za n število rekurzivnih klicev je časovna zapletenost O (n).

Kaj je iteracija?

Iteracija je sklop navodil, ki se ponavlja vedno znova, dokler navedeni pogoj ni pravi. Iteracija se lahko doseže z uporabo „za zanko“, „zanka med izvajanjem“ ali „med zanko“. Sintaksa »za zanko« je naslednja.

za (inicializacija; pogoj; sprememba)

// izjave;

Slika 02: "za diagram toka zanke"

Korak inicializacije se najprej izvede. Ta korak je razglasitev in inicializacija spremenljivk za nadzor zanke. Če je pogoj resničen, se izjave znotraj kodrastih naramnic izvedejo. Te izjave se izvajajo, dokler pogoj ni resničen. Če je pogoj napačen, kontrolnik preide na naslednjo izjavo po "za zanko". Po izvedbi stavkov znotraj zanke se krmilnik spremeni v razdelek za spreminjanje. Gre za posodobitev spremenljivke za nadzor zanke. Nato se stanje še enkrat preveri. Če je pogoj resničen, se bodo izjave znotraj kodrastih naramnic izvedle. Tako se "za zanko" ponavlja.

V "medtem ko zanka", stavki znotraj zanke se izvajajo, dokler je pogoj resničen.

medtem ko (pogoj)

// izjave

V zanki "med delom", stanje se preveri na koncu zanke. Torej, zanka se izvede vsaj enkrat.

narediti

// izjave

medtem ko (pogoj)

Program za iskanje faktorja 3 (3!) Z uporabo iteracije ("za zanko") je naslednji.

int main ()

intn = 3, faktororial = 1;

inti;

za (i = 1; i<=n ; i++)

faktororial = faktororial * i;

printf ("Faktororial je% d \ n", faktororial);

vrne 0;

Kakšne so podobnosti med rekurzijo in iteracijo?

• Oboje je tehnika reševanja težave.
• Nalogo lahko rešimo bodisi v rekurziji bodisi v iteraciji.

Kakšna je razlika med rekurzijo in iteracijo?

Rekurzija vs ponovitev
Rekurzija je način klicanja funkcije znotraj iste funkcije.	Iteracija je sklop navodil, ki se ponavlja, dokler navedeni pogoj ni resničen.
Vesoljska zapletenost
Prostornost kompleksnosti rekurzivnih programov je večja od iteracij.	Prostornost kompleksnosti je v iteracijah manjša.
Hitrost
Rekurzijska izvedba je počasna.	Običajno je iteracija hitrejša od rekurzije.
Pogoj
Če ne obstaja pogoj prenehanja, lahko pride do neskončne rekurzije.	Če stanje nikoli ne postane napačno, bo to neskončna iteracija.
Zložite
V rekurziji se sklad uporablja za shranjevanje lokalnih spremenljivk, ko se prikliče funkcija.	V iteraciji se sklad ne uporablja.
Čitljivost kode
Rekurzivni program je bolj berljiv.	Iterativni program je težje brati kot rekurziven.

Povzetek - rekurzija vs ponovitev

Ta članek obravnava razliko med rekurzijo in iteracijo. Oboje je mogoče uporabiti za reševanje težav s programiranjem. Razlika med rekurzijo in iteracijo je v tem, da je rekurzija mehanizem za poklic funkcije znotraj iste funkcije in iteracijo, da izvede niz navodil večkrat, dokler navedeni pogoj ni pravi. Če je težavo mogoče rešiti v rekurzivni obliki, jo je mogoče rešiti tudi z iteracijami.

Prenesite PDF različico Recursion vs Iteration

Lahko prenesete PDF različico tega članka in jo uporabljate za namene brez povezave, kot je navedeno v navodilu. Prosimo, prenesite PDF različico tukaj Razlika med rekurzijo in ponovitvijo

Referenca:

1.Point, Vadnice. "Podatkovne strukture in osnove algoritmov.", Tutorials Point, 15. avgust 2017. Na voljo tukaj 
2.natehnologije. „Rekurzija v funkcijah C | C Language Tutorial ”YouTube, YouTube, 12. septembra 2016. Na voljo tukaj  
3.yusuf shakeel. „Algoritem rekurzije | Faktororial - vodnik po korakih ”YouTube, YouTube, 14. oktober 2013. Na voljo tukaj  

Vljudnost slik:

1.'CPT-Recursion-Factorial-Code'By Pluke - Lastno delo, (Public Domain) prek Commons Wikimedia 
2. 'Za-zanko-diagram' Če ni avtorja, ki je strojno berljiv - predpostavljeno je lastno delo. (CC BY-SA 2.5) prek Wikimedije Commons