Diferența cheie – recursivitate vs iterație
Recursiunea și iterația pot fi folosite pentru a rezolva problemele de programare. Abordarea rezolvării problemei folosind recursiunea sau iterația depinde de modul de rezolvare a problemei. Diferența cheie dintre recursivitate și iterație este că recursiunea este un mecanism de apelare a unei funcții î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ă. Recursiunea și iterația sunt tehnici majore pentru dezvoltarea algoritmilor și crearea de aplicații software.
Ce este recursiunea?
Când o funcție se autoinvocă în cadrul funcției, este cunoscută sub numele de recursivitate. Există două tipuri de recursivitate. Ele sunt recursivitate finită și recursivitate infinită. Recursiunea finită are o condiție de terminare. Recursiunea infinită nu are o condiție de terminare.
Recursiunea poate fi explicată folosind programul de calculare a factorilor.
n!=n(n-1)!, dacă n>0
n!=1, dacă n=0;
Consultați codul de mai jos pentru a calcula factorialul 3(3!=321).
intmain () {
int valoare=factorial (3);
printf(„Factorialul este %d\n”, valoare);
return 0;
}
intfactorial (intn) {
if(n==0) {
retur 1;
}
else {
return n factorial(n-1);
}
}
Când apelați factorial (3), acea funcție va apela factorial (2). Când apelați factorial (2), acea funcție va apela factorial (1). Atunci factorialul (1) va numi factorial (0). factorial (0) va returna 1. În programul de mai sus, condiția n==0 din „blocul dacă” este condiția de bază. Conform Asemenea, funcția factorială este apelată din nou și din nou.
Funcțiile recursive sunt legate de stiva. Î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 apelată. Când funcția este apelată, controlul este dat funcției apelate. După ce execuția funcției este finalizată, controlul revine la principal. Apoi programul principal continuă. Deci, creează o înregistrare de activare sau un cadru de stivă pentru a continua execuția.
Figura 01: Recursiune
În programul de mai sus, la apelarea factorialului (3) din main, creează o înregistrare de activare în stiva de apeluri. Apoi, cadrul de stivă factorial (2) este creat deasupra stivei și așa mai departe. Înregistrarea de activare păstrează informații despre variabilele locale etc. De fiecare dată când funcția este apelată, un nou set de variabile locale este creat în partea de sus a stivei. Aceste cadre stive pot încetini viteza. La fel și în recursivitate, o funcție se autoinvocă. Complexitatea timpului pentru o funcție recursivă este găsită de numărul de ori, funcția este apelată. Complexitatea timpului pentru un apel de funcție este O(1). Pentru n număr de apeluri recursive, complexitatea timpului este O(n).
Ce este iterația?
Iterația este un bloc de instrucțiuni care se repetă din nou și din nou până când condiția dată este adevărată. Iterația poate fi realizată folosind „bucla for”, „bucla do-while” sau „bucla în timp ce”. Sintaxa „for loop” este următoarea.
pentru (inițializare; condiție; modificare) {
// declarații;
}
Figura 02: „for diagrama fluxului buclei”
Pasul de inițializare se execută primul. Acest pas este de a declara și inițializa variabilele de control al buclei. Dacă condiția este adevărată, instrucțiunile din interiorul acoladelor sunt executate. Acele 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ă „bucla for”. După executarea instrucțiunilor în interiorul buclei, controlul trece la secțiunea de modificare. Este pentru a actualiza variabila de control al buclei. Apoi starea este verificată din nou. Dacă condiția este adevărată, instrucțiunile din interiorul acoladelor se vor executa. În acest fel, „bucla for” se repetă.
În „bucla în timp ce”, instrucțiunile din interiorul buclei se execută până când condiția este adevărată.
în timp ce (condiție){
//declarații
}
În bucla „do-while”, condiția este verificată la sfârșitul buclei. Deci, bucla se execută cel puțin o dată.
face{
//declarații
} while(condiție)
Programul pentru a găsi factorialul lui 3 (3!) folosind iterația („bucla pentru”) este următorul.
int main(){
intn=3, factorial=1;
inti;
for(i=1; i<=n; i++){
factorial=factoriali;
}
printf(„Factorialul este %d\n”, factorial);
return 0;
}
Care sunt asemănările dintre recursivitate și iterație?
- Ambele sunt tehnici pentru a rezolva o problemă.
- Sarcina poate fi rezolvată fie prin recursivitate, fie prin iterație.
Care este diferența dintre recursivitate și iterație?
Recursiune vs iterație |
|
| Recursiunea este o metodă de a apela o funcție în cadrul aceleiași funcții. | Iterația este un bloc de instrucțiuni care se repetă până când condiția dată este adevărată. |
| Complexitatea spațiului | |
| Complexitatea spațială a programelor recursive este mai mare decât iterațiile. | Complexitatea spațiului este mai mică în iterații. |
| Viteza | |
| Execuția recursiunii este lentă. | În mod normal, iterația este mai rapidă decât recursiunea. |
| Condiție | |
| Dacă nu există nicio condiție de terminare, poate exista o recursivitate infinită. | Dacă condiția nu devine niciodată falsă, va fi o iterație infinită. |
| Stiva | |
| În recursivitate, stiva este folosită pentru a stoca variabile locale atunci când funcția este apelată. | Într-o iterație, stiva nu este utilizată. |
| Lizibilitatea codului | |
| Un program recursiv este mai ușor de citit. | Programul iterativ este mai greu de citit decât un program recursiv. |
Rezumat – Recursie vs Iterație
Acest articol a discutat despre diferența dintre recursivitate și iterație. Ambele pot fi folosite pentru a rezolva probleme de programare. Diferența dintre recursivitate și iterație este că recursiunea este un mecanism de apelare a unei funcții în cadrul aceleiași funcții și de iterație pentru a executa un set de instrucțiuni în mod repetat până când condiția dată este adevărată. Dacă o problemă poate fi rezolvată în formă recursivă, poate fi rezolvată și folosind iterații.
Descărcați versiunea PDF a recursiunii vs iterație
Puteți descărca versiunea PDF a acestui articol și o puteți utiliza în scopuri offline, conform nota de citare. Vă rugăm să descărcați versiunea PDF aici Diferența dintre recurență și iterație
