Kulcskülönbség – Rekurzió vs iteráció
A rekurzió és az iteráció programozási problémák megoldására használható. A probléma rekurzióval vagy iterációval történő megoldásának megközelítése a probléma megoldásának módjától függ. A legfontosabb különbség a rekurzió és az iteráció között az, hogy a rekurzió egy olyan mechanizmus, amely egy függvényt hív meg ugyanazon a függvényen belül, míg az iteráció egy utasításkészletet hajt végre ismételten, amíg az adott feltétel igaz. A rekurzió és az iteráció az algoritmusok fejlesztésének és a szoftveralkalmazások készítésének fő technikái.
Mi az a rekurzió?
Amikor egy függvény meghívja magát a függvényen belül, azt Rekurziónak nevezik. A rekurziónak két típusa van. Ezek véges rekurzió és végtelen rekurzió. A véges rekurziónak van egy befejező feltétele. A végtelen rekurziónak nincs befejező feltétele.
A rekurzió magyarázható a faktoriális számítási programmal.
n!=n(n-1)!, ha n>0
n!=1, ha n=0;
A 3(3!=321) faktoriális kiszámításához használja az alábbi kódot.
intmain () {
int érték=tényezős (3);
printf("A tényezõ %d\n", érték);
vissza 0;
}
intfactorial (intn) {
if(n==0) {
vissza 1;
}
egyéb {
return n faktoriális(n-1);
}
}
A faktoriális (3) meghívásakor ez a függvény a faktori alt (2) fogja hívni. A faktoriális (2) meghívásakor az a függvény hívja a faktori alt (1). Ekkor a faktoriális (1) a faktori alt (0) hívja. A faktoriális (0) 1-et ad vissza. A fenti programban az „if blokk” n==0 feltétele az alapfeltétel. A Hasonló szerint a faktoriális függvényt újra és újra meghívják.
A rekurzív függvények a veremhez kapcsolódnak. C nyelven a főprogramnak számos funkciója lehet. Tehát a main () a hívó függvény, a főprogram által meghívott függvény pedig a hívott függvény. A függvény meghívásakor a vezérlést a hívott függvény kapja meg. A funkció végrehajtása után a vezérlés visszakerül a főbe. Ezután a fő program folytatódik. Tehát létrehoz egy aktiválási rekordot vagy egy verem keretet a végrehajtás folytatásához.
01. ábra: Rekurzió
A fenti programban a faktoriális (3) főről történő hívásakor aktiválási rekordot hoz létre a hívási veremben. Ezután faktoriális (2) veremkeret jön létre a verem tetején, és így tovább. Az aktiválási rekord információkat tárol a helyi változókról stb. A függvény minden egyes meghívásakor egy új helyi változókészlet jön létre a verem tetején. Ezek a veremkockák lelassíthatják a sebességet. Ugyanígy a rekurzióban a függvény meghívja magát. A rekurzív függvény időbonyolultságát a függvény meghívásának száma alapján határozzuk meg. Egy függvényhívás időbonyolultsága O(1). N számú rekurzív hívás esetén az időbonyolultság O(n).
Mi az az iteráció?
Az iteráció utasítások blokkja, amely újra és újra ismétlődik, amíg a megadott feltétel igaz. Az iteráció a „for loop”, a „do-while loop” vagy a „while loop” használatával érhető el. A „for loop” szintaxis a következő.
for (inicializálás; feltétel; módosítás) {
// nyilatkozatok;
}
02. ábra: „hurok folyamatábra”
Az inicializálási lépés fut először. Ez a lépés a hurokvezérlő változók deklarálása és inicializálása. Ha a feltétel igaz, a kapcsos zárójelben lévő utasítások végrehajtásra kerülnek. Ezek az állítások addig futnak, amíg a feltétel igaz. Ha a feltétel hamis, a vezérlő a következő utasításra lép a „for ciklus” után. A cikluson belüli utasítások végrehajtása után a vezérlő a módosító szakaszra lép. Ez a hurokvezérlő változó frissítése. Ezután újra ellenőrzik az állapotot. Ha a feltétel igaz, a kapcsos zárójelben lévő utasítások végrehajtásra kerülnek. Így a „for ciklus” ismétlődik.
A „while ciklusban” a cikluson belüli utasítások addig futnak, amíg a feltétel igaz.
közben (feltétel){
//állítások
}
A „do-while” ciklusban a feltétel a ciklus végén kerül ellenőrzésre. Tehát a ciklus legalább egyszer végrehajtódik.
do{
//állítások
} while(feltétel)
A 3 (3!) faktoriális iterációval („for ciklus”) megkeresésére szolgáló program a következő.
int main(){
intn=3, faktoriális=1;
inti;
for(i=1; i<=n; i++){
faktoriális=faktoriálisi;
}
printf(“A faktor %d\n”, faktoriális);
vissza 0;
}
Mi a hasonlóság a rekurzió és az iteráció között?
- Mindkét technika egy probléma megoldására.
- A feladat rekurzióval vagy iterációval is megoldható.
Mi a különbség a rekurzió és az iteráció között?
Rekurzió vs iteráció |
|
| A rekurzió egy függvény meghívásának módszere ugyanazon a függvényen belül. | Az iteráció egy utasításblokk, amely addig ismétlődik, amíg a megadott feltétel igaz. |
| Térkomplexitás | |
| A rekurzív programok térbeli összetettsége nagyobb, mint az iterációk. | A tér összetettsége kisebb az iterációk során. |
| Sebesség | |
| A rekurzió végrehajtása lassú. | Általában az iteráció gyorsabb, mint a rekurzió. |
| Állapot | |
| Ha nincs lezárási feltétel, akkor végtelen rekurzió lehet. | Ha a feltétel soha nem válik hamissá, végtelen iteráció lesz. |
| Stack | |
| Rekurzióban a verem a helyi változók tárolására szolgál a függvény meghívásakor. | Az iteráció során a verem nem kerül felhasználásra. |
| Kód olvashatósága | |
| A rekurzív program jobban olvasható. | Az iteratív programot nehezebb olvasni, mint egy rekurzív programot. |
Összegzés – Rekurzió vs iteráció
Ez a cikk a rekurzió és az iteráció közötti különbséget tárgy alta. Mindkettő használható programozási problémák megoldására. A rekurzió és az iteráció közötti különbség az, hogy a rekurzió egy olyan mechanizmus, amely ugyanazon a függvényen belül meghív egy függvényt, és iterálja azt, hogy ismételten végrehajtson egy utasításkészletet, amíg az adott feltétel igaz. Ha egy probléma megoldható rekurzív formában, akkor iterációkkal is megoldható.
A Recursion vs Iteration PDF verziójának letöltése
Letöltheti ennek a cikknek a PDF-verzióját, és offline célokra használhatja az idézet jegyzetének megfelelően. Kérjük, töltse le a PDF verziót innen: Különbség a rekurzió és az iteráció között
