Diferența cheie - recursivitate vs iterație
Recursivitatea și iterația pot fi utilizate pentru rezolvarea problemelor de programare. Abordarea rezolvării problemei utilizând recursivitate sau iterație depinde de modul de rezolvare a problemei. Diferența cheie între recursivitate și iterație este că recursivitatea este un mecanism pentru a apela o funcție în cadrul aceleiași funcții, în timp ce iterația este de a executa un set de instrucțiuni în mod repetat până când condiția dată este adevărată. Recursivitatea și iterația sunt tehnici majore pentru dezvoltarea algoritmilor și construirea aplicațiilor software.
CUPRINS
1. Prezentare generală și diferența cheie
2. Ce este recursiunea
3. Ce este iterația
4. Asemănări între recursivitate și iterație
5. Comparație side by side - Recursie vs iterație în formă tabelară
6. Rezumat
Ce este recursivitatea?
Când o funcție se numește singură în cadrul funcției, este cunoscută sub numele de Recursivitate. Există două tipuri de recursivitate. Sunt recursivitate finită și recursivitate infinită. Recursivitatea finită are o condiție de terminare. Recursivitatea infinită nu are o condiție de terminare.
Recursivitatea poate fi explicată folosind programul pentru a calcula factorialele.
n! = n * (n-1) !, dacă n> 0
n! = 1, dacă n = 0;
Consultați codul de mai jos pentru a calcula factorialul de 3 (3! = 3 * 2 * 1).
intmain () {
valoarea int = factorială (3);
printf („Factorialul este% d / n”, valoare);
retur 0;
}
intfactorial (intn) {
if (n == 0) {
retur 1;
}
altceva {
returnează n * factorial (n-1);
}
}
Când se apelează factorial (3), acea funcție va apela factorial (2). Când se apelează factorial (2), acea funcție va apela factorial (1). Apoi factorial (1) va numi factorial (0). factorial (0) va reveni 1. În programul de mai sus, n == 0 condiție în „dacă bloc” este condiția de bază. Conform Același lucru, funcția factorială este apelată din nou și din nou.
Funcțiile recursive sunt legate de stivă. În C, programul principal poate avea multe funcții. Deci, main () este funcția de apelare, iar funcția care este apelată de programul principal este funcția numită. Când funcția este apelată, controlul este dat funcției apelate. După finalizarea executării funcției, controlul este returnat la main. Apoi programul principal continuă. Deci, creează o înregistrare de activare sau un cadru de stivă pentru a continua execuția.
Figura 01: Recursivitate
În programul de mai sus, când se apelează factorial (3) din main, creează o înregistrare de activare în teancul de apeluri. Apoi, cadrul de stivă factorial (2) este creat deasupra stivei și așa mai departe. Înregistrarea activării păstrează informații despre variabilele locale etc. De fiecare dată când funcția este apelată, un nou set de variabile locale sunt create în partea de sus a stivei. Aceste cadre de stivă pot încetini viteza. La fel, în recursivitate, o funcție se numește singură. Complexitatea timpului pentru o funcție recursivă este găsită de numărul de ori, funcția este numită. Complexitatea de timp pentru o singură funcție este O (1). Pentru n număr de apeluri recursive, complexitatea timpului este O (n).
Ce este iterația?
Iterarea este un bloc de instrucțiuni care se repetă din nou și din nou până când condiția dată este adevărată. Iterarea poate fi realizată folosind „pentru buclă”, „buclă do-while” sau „buclă while”. Sintaxa „pentru buclă” este următoarea.
pentru (inițializare; condiție; modificare) {
// declaratii;
}
Figura 02: „pentru diagrama fluxului de buclă”
Pasul de inițializare se execută mai întâi. Acest pas este de a declara și inițializa variabilele de control al buclei. Dacă condiția este adevărată, se execută instrucțiunile din interiorul acoladelor. Aceste declarații se execută până când condiția este adevărată. Dacă condiția este falsă, controlul trece la următoarea instrucțiune după „for loop”. După executarea instrucțiunilor din interiorul buclei, controlul trece la secțiunea de modificare. Este pentru a actualiza variabila de control buclă. Apoi starea este verificată din nou. Dacă condiția este adevărată, instrucțiunile din interiorul acoladelor vor fi executate. În acest fel iterația „pentru buclă”.
În „while loop”, declarațiile din buclă se execută până când condiția este adevărată.
while (condiție) {
// declarații
}
În bucla „do-while”, starea este verificată la sfârșitul buclei. Deci, bucla se execută cel puțin o dată.
do{
// declarații
} while (condiție)
Programul pentru a găsi factorialul de 3 (3!) Folosind iterația („pentru buclă”) este după cum urmează.
int main () {
intn = 3, factorial = 1;
inti;
pentru (i = 1; i <= n; i ++) {
factorial = factorial * i;
}
printf („Factorial este% d / n”, factorial);
retur 0;
}
Care sunt asemănările dintre recursivitate și iterație?
- Ambele sunt tehnici pentru rezolvarea unei probleme.
- Sarcina poate fi rezolvată fie prin recursivitate, fie prin iterație.
Care este diferența dintre recursivitate și iterație?
Difuzarea articolului din mijloc înainte de tabel
Recursivitate vs Iterare |
|
| Recursivitatea este o metodă de apelare a unei funcții în cadrul aceleiași funcții. | Iterarea este un bloc de instrucțiuni care se repetă până când condiția dată este adevărată. |
| Complexitatea spațială | |
| Complexitatea spațială a programelor recursive este mai mare decât iterațiile. | Complexitatea spațiului este mai mică în iterații. |
| Viteză | |
| Executarea recursivă este lentă. | În mod normal, iterația este mai rapidă decât recursivitatea. |
| Condiție | |
| Dacă nu există o condiție de terminare, poate exista o recursivitate infinită. | Dacă condiția nu devine niciodată falsă, va fi o iterație infinită. |
| Grămadă | |
| În recursivitate, stiva este utilizată pentru a stoca variabile locale atunci când funcția este apelată. | Într-o iterație, stiva nu este utilizată. |
| Citibilitatea codului | |
| Un program recursiv este mai lizibil. | Programul iterativ este mai greu de citit decât un program recursiv. |
Rezumat - Recursivitate vs Iterare
Acest articol a discutat despre diferența dintre recursivitate și iterație. Ambele pot fi utilizate pentru rezolvarea problemelor de programare. Diferența dintre recursivitate și iterație este că recursivitatea este un mecanism pentru a apela o funcție din aceeași funcție și iterația acesteia pentru a executa în mod repetat un set de instrucțiuni până când condiția dată este adevărată. Dacă o problemă poate fi rezolvată în formă recursivă, ea poate fi rezolvată și cu iterații.
Descărcați versiunea PDF a Recursive vs Iteration
Puteți descărca versiunea PDF a acestui articol și o puteți folosi în scopuri offline, conform notei de citare. Vă rugăm să descărcați versiunea PDF aici Diferența dintre recursivitate și iterație
