Meniu

Recursivitate în C ++

recursion c

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Explorați totul despre recursivitate în C ++ cu exemple clasice.

În tutorialul nostru anterior, am aflat mai multe despre funcțiile din C ++.

În afară de utilizarea funcțiilor pentru descompunerea codului în subunități și simplificarea și lizibilitatea codului, funcțiile sunt utile în diverse alte aplicații, inclusiv rezolvarea problemelor în timp real, calcul matematic și statistic.

Pe măsură ce dezvoltăm aplicații mai complexe în C ++, întâlnim multe cerințe, astfel încât trebuie să folosim mai multe concepte speciale de C ++. Recursivitatea este un astfel de concept.

=> Vizitați aici pentru lista completă de tutoriale C ++.

RECURSIE ÎN C ++

În acest tutorial, vom afla mai multe despre recursivitate, unde și de ce este folosit împreună cu câteva exemple clasice C ++ care implementează recursivitatea.

Ce veți învăța:

Ce este recursivitatea?

Recursivitatea este un proces în care o funcție se numește singură. Funcția care implementează recursivitatea sau se numește singură se numește funcție recursivă. În recursivitate, funcția recursivă se apelează mereu și continuă până când se îndeplinește o condiție finală.

Imaginea de mai jos descrie modul în care funcționează recursivitatea:

Funcționarea recursivității

După cum vedem în diagrama de mai sus, funcția principală numește o funcție, funct (). Funcția funct () la rândul său se numește în interiorul definiției sale. Așa funcționează recursivitatea. Acest proces de apelare a funcției în sine va continua până când vom furniza o condiție de terminare care o va face să se încheie.

De obicei, oferim ramificarea codului în timp ce implementăm recursivitatea, astfel încât să oferim o condiție care va declanșa recursiunea și alta pentru a efectua o execuție normală.

Starea bazei recursive

Când se efectuează recursivitatea, se oferă soluția la cazul de bază sau la cazul final, iar soluțiile la probleme mai mari sunt construite pe baza soluțiilor la probleme mai mici.

Să luăm în considerare un exemplu clasic de recursivitate, notația factorială.

Știm că matematic factorialul unui număr n este:

n! = nxn-1x… .x0!
dat fiind acel 0! = 1;

Deci factorial pentru n = 3 va fi 3! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

Deci, programatic, putem exprima acest calcul astfel:

int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }

Astfel, așa cum se arată mai sus, am exprimat calculul de mai sus al unui factorial într-un apel funcțional recursiv. Vedem că dacă numărul n este mai mic sau egal cu 1, returnăm 1 în loc de un apel recursiv. Aceasta se numește condiție / caz de bază pentru factorial care permite oprirea recursiunii.

Prin urmare, condiția de bază decide de câte ori o funcție recursivă ar trebui să se numească. Aceasta înseamnă că putem calcula foarte bine factorialul unui număr mai mare exprimându-l în termeni de numere mai mici până când se ajunge la clasa de bază.

Dat mai jos este un exemplu perfect pentru a calcula factorialul unui număr:

#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout<

Ieșire:

Introduceți numărul a cărui factorială trebuie calculată: 10
10! = 3628800

În exemplul de mai sus, implementăm recursivitatea. Luăm numărul a cărui factorială se găsește din intrarea standard și apoi o trecem la funcția factorială.

În funcția factorială, am dat condiția de bază ca (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Alocarea memoriei pentru apelul recursiv

Știm că atunci când se efectuează un apel funcțional, starea funcției apelante este stocată în stivă și când se finalizează un apel funcțional, starea respectivă este restabilită înapoi, astfel încât programul să poată continua execuția.

Când se efectuează un apel de funcție recursivă, starea sau memoria pentru funcția apelată este alocată în partea de sus a stării funcției de apelare și se face o copie diferită a variabilelor locale pentru fiecare apel de funcție recursivă.

Când se atinge condiția de bază, funcția revine la funcția de apelare și memoria este alocată și procesul continuă.

Stack Overflow În recursivitate

Când recursivitatea continuă pentru o perioadă nelimitată de timp, aceasta poate duce la o revărsare a stivei.

Când poate continua recursivitatea astfel? O situație este când nu specificăm condiția de bază. O altă situație este când condiția de bază nu este atinsă în timpul executării unui program.

De exemplu,modificăm programul factorial de mai sus și îi schimbăm starea de bază.

int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }

În codul de mai sus, am schimbat condiția de bază în (n == 1000). Acum, dacă dăm numărul n = 10, putem concluziona că condiția de bază nu va ajunge niciodată. În acest fel, la un moment dat, memoria din stivă va fi epuizată, rezultând astfel o revărsare a stivei.

Prin urmare, în timp ce proiectăm programe recursive, trebuie să fim atenți la starea de bază pe care o oferim.

Direct Vs Recursivitate indirectă

Până acum, în recursivitate, am văzut funcția numindu-se. Aceasta este recursiunea directă.

Există un alt tip de recursivitate, adică recursivitatea indirectă. În acest sens, o funcție apelează o altă funcție și apoi această funcție apelează funcția de apelare. Dacă f1 și f2 sunt două funcții. Apoi f1 apelează f2 și f2, la rândul său, apelează f1. Aceasta este o recursivitate indirectă.

care este cel mai bun downloader de muzică pentru pc

L și noi ne revizuim programul factorial pentru a demonstra recursivitatea directă.

#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout<

Ieșire:

Introduceți numărul a cărui factorială trebuie calculată: 5
5! = 120

În exemplul de mai sus, am arătat recursivitate indirectă. Funcția principală numește factorial_a. Factorial_a apelează factorial_b. La rândul său, factorial_b apelează factorial_a. Vedem că rezultatul programului nu este afectat.

Recursivitate cu coadă și fără coadă

O funcție recursivă cu coadă este o funcție recursivă în care ultimul apel este executat în funcție.

De exemplu, ia în considerare următoarea funcție.

void display(int n){ if(n<=1) return; cout<<” ”<

În exemplul de mai sus, afișajul este o funcție recursivă cu coadă, astfel încât acesta este ultimul apel de funcție.

Funcțiile cu coadă sunt considerate mai bune decât funcțiile recursive fără coadă, deoarece pot fi optimizate de compilator. Motivul este că, deoarece apelul recursiv cu coadă este ultima instrucțiune din funcție, nu există niciun cod care să fie executat după acest apel.

Ca urmare, nu este necesară salvarea cadrului curent al stivei pentru funcție.

Pro / Contra recursivității peste programarea iterativă

Programele recursive oferă cod compact și curat. Un program recursiv este un mod simplu de a scrie programe. Există unele probleme inerente, cum ar fi factorial, secvența Fibonacci, turnurile din Hanoi, traversarea copacilor etc., care necesită recursivitate pentru rezolvare.

Cu alte cuvinte, acestea sunt rezolvate eficient cu recursivitate. Ele pot fi, de asemenea, rezolvate cu programare iterativă folosind stive sau alte structuri de date, dar există șanse să devină mai complexe de implementat.

Puterile de rezolvare a problemelor programării recursive și iterative sunt aceleași. Cu toate acestea, programele recursive ocupă mai mult spațiu de memorie, deoarece toate apelurile funcționale trebuie stocate în stivă până când se potrivesc carcasa de bază.

Funcțiile recursive au, de asemenea, o cheltuială temporală din cauza prea multor apeluri de funcții și valori de returnare.

Exemple de recursivitate

În continuare, vom implementa câteva exemple de programare recursivă.

Seria Fibonacci

Seria Fibonacci este secvența care este dată ca

0 1 1 2 3 5 8 13 ……

După cum se arată mai sus, primele două numere din seria Fibonacci sunt 0 și 1. Următorul număr din secvență este suma celor două numere anterioare.

Să implementăm această serie folosind Recursivitate.

#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '<

Ieșire:

Introduceți numărul de elemente pentru seria Fibonacci: 10
Seria Fibonacci pentru 10 numere: 0 1 1 2 3 5 8 13 21 34

În acest exemplu, am folosit un apel recursiv pentru a genera secvența Fibonacci. Vedem că primele două numere fiind constante sunt direct tipărite și pentru următoarele numere din secvență folosim o funcție recursivă.

Palindrom

Un număr palindrom este un număr care, atunci când este citit în sens invers, este același cu cel citit în direcția stânga-dreapta.

De exemplu, numărul 121 în timp ce citește de la stânga la dreapta și de la dreapta la stânga citește la fel, adică 121. Prin urmare, 121 este un palindrom.

Numărul 291, când citește de la dreapta la stânga, adică în ordine inversă, citește 192. Prin urmare, 291 nu este un palindrom.

#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '<

Ieșire:

Introduceți numărul pentru a verifica palindromul: 6556
Numărul 6556 este un palindrom

Captura de ecran pentru același lucru este prezentată mai jos.

Recursivitate - Palindrom

În programul de mai sus, citim numărul de intrare din intrarea standard. Apoi trecem acest număr la o funcție recursivă pentru a inversa cifrele unui număr. Dacă cifrele inversate și numărul de intrare sunt aceleași, atunci numărul este un palindrom.

Concluzie

Cu aceasta, am terminat cu recursivitatea. În acest tutorial, am studiat programarea recursivă, funcția recursivă, avantajele / dezavantajele acesteia, împreună cu diferite exemple în detaliu.

În afară de aceste exemple, recursivitatea este, de asemenea, utilizată în rezolvarea unor probleme standard, cum ar fi traversările (inorder / preorder / postorder), turnurile din Hanoi, traversarea BFS etc.

=> Vizitați aici pentru a afla C ++ de la zero.

Lectură recomandată

^