Ce este recursiunea și cum o folosești?

Recursiunea este un concept de programare distractiv, dar poate fi puțin dificil de învățat. Recursiunea înseamnă pur și simplu ceva care se repetă. Dacă doriți să vedeți un exemplu obraznic de recursivitate, încercați să căutați recursiunea pe Google. Veți găsi un ou de Paște în care sugestiile rezultatelor căutării sunt recursive. Dacă, pe de altă parte, doriți să învățați cum să codificați o funcție recursivă, citiți mai departe!

Ce este o funcție recursivă?

O funcție recursivă este o funcție care se autoinvocă. În esență, creați o buclă cu o funcție. După cum vă puteți imagina, acestea pot fi funcții dificil de scris. Nu doriți ca codul dvs. să ruleze pentru totdeauna.

Similar cu o buclă, o funcție recursivă va fi controlată de o condiție. Odată ce condiția este îndeplinită, funcția încetează să se mai apeleze, ceea ce oprește bucla. Acesta este modul în care puteți crea o funcție care se autoapelează fără ca aceasta să ruleze pentru totdeauna.

Deși o funcție recursivă acționează ca o buclă, ea este executată de computer în mod diferit. Deci, unii algoritmi sunt mai eficienți într-o buclă, iar alții beneficiază de o funcție recursivă. Dar înainte de a ne uita la cum să folosiți o funcție recursivă, trebuie să știți cum să scrieți una.

Cum se scrie o functie recursiva

Toate funcțiile recursive au aceeași structură de bază:

FUNCTION name IF condition THEN RETURN result ELSE CALL FUNCTION name END FUNCTION

Exemplul de mai sus este scris în pseudo-cod. Acesta conturează structura funcției, care poate fi aplicată oricărei limbi. Pentru simplitate, în acest articol, ne vom concentra pe Python.

Primul lucru de remarcat despre o funcție recursivă este că atunci când condiția este îndeplinită, funcția iese din recursivitate. Aceasta înseamnă că atunci când scrieți o funcție recursivă, primul lucru pe care veți dori să determinați este când să opriți recursiunea.

Dacă condiția nu este îndeplinită, funcția se va autoapela. Deci, dacă doriți să trimiteți informații la următoarea buclă, va trebui să o trimiteți ca argument în funcția dvs. Acest lucru poate oferi funcțiilor recursive mult mai multă putere.

Înrudit: Ce este o funcție în programare?

Exemplu de funcție recursive în Python

Va fi mult mai ușor de înțeles cum funcționează recursiunea când o vei vedea în acțiune. Pentru a o demonstra, să scriem o funcție recursivă care returnează factorialul unui număr.

Factorialii returnează produsul unui număr și al tuturor numerelor întregi dinaintea acestuia. De exemplu, factorialul lui 5 este 5 x 4 x 3 x 2 x 1 sau 120.

def factorialFunction(numberToMultiply): if numberToMultiply == 1 : return 1 else : return numberToMultiply * factorialFunction(numberToMultiply - 1) result = factorialFunction(3) print(result) //Outputs: 6

Programul de mai sus vă va oferi rezultatul 6, care este factorialul numărului 3. Acest lucru poate fi puțin confuz la început. Va ajuta dacă parcurgem programul pas cu pas.

1. Când funcția este apelată, numberToMultiply este egal cu 3.
2. Condiția nu este îndeplinită, așa că trecem la starea else .
3.  Funcția noastră returnează 3 *, dar este apoi întreruptă. Trebuie să se autoinvoce pentru a determina restul valorii pe care o returnează.
4. Când funcția este apelată de data aceasta, valoarea numărului pentru înmulțire este egală cu 2.
5. Condiția nu este îndeplinită, așa că trecem la starea else.
6. Funcția noastră returnează 2 *, dar este apoi întreruptă. Trebuie să se autoinvoce pentru a determina restul valorii pe care o returnează.
7. Funcția este apelată din nou. De data aceasta, valoarea numberToMultiply este egală cu 1.
8. Condiția noastră dacă este îndeplinită. Funcția returnează 1.
9. Funcția de la pasul 6 poate reveni acum 2 * 1 la funcția de la pasul 3.
10. Funcția de la pasul trei poate returna acum 3 * 2 * 1, care este 6.

Recursiunea este un concept complicat. Poate fi util să ne gândim la asta ca stivuirea unei funcții peste o altă funcție. Odată ce o funcție este în sfârșit rezolvată, poate trimite informațiile înapoi în stivă, până când toate funcțiile își au răspunsul.

Acesta este de fapt ceea ce face computerul dvs. Când apelați funcția, aceasta este păstrată în memorie până când este returnată. Aceasta înseamnă că funcțiile recursive pot folosi mult mai multă memorie decât o buclă.

Deci, s-ar putea să nu fie eficient să scrieți bucle ca funcții recursive, dar este o modalitate excelentă de a exersa construirea lor. Ar trebui să puteți codifica buclele ca funcții recursive cu rezultate similare.

Un exemplu despre cum să convertiți o buclă într-o funcție recursiv

print("Enter an even number:") i = int(input()) while (i % 2) != 0 : print("That number is not even. Please enter a new number:") i = int(input())

Această buclă poate fi, de asemenea, scrisă recursiv ca:

def recursiveFunction(number) : if (number % 2) == 0 : return number else: print("That number is not even. Please enter a new number:") recursiveFunction(int(input())) print("Enter and even number:") i = recursiveFunction(int(input()))

Primul pas este să determinați când doriți să se oprească funcția. În acest caz, dorim să se oprească odată ce este introdus un număr par. În exemplul nostru, numărul urmărește intrarea utilizatorului. Dacă introduc un număr par, returnăm numărul. În caz contrar, vom continua să cerem un număr nou.

Pentru a configura bucla, apelăm din nou funcția noastră. Dar de data aceasta, numărul pe care îl trecem la următoarea funcție este noul număr introdus de utilizator. Următorul apel de funcție va verifica numărul.

Aceasta este o funcție foarte proastă! Da, verifică dacă numărul este par, ca bucla noastră, dar nu este eficient. De fiecare dată când utilizatorul introduce un număr impar, funcția este păstrată în memorie și este apelată o nouă funcție. Dacă faci asta de destule ori, vei rămâne fără memorie!

Înrudit: Exemple de bază Python care vă vor ajuta să învățați rapid

Un exemplu real al unei funcții recursive

Exemplele de mai sus au fost exemple bune de când nu trebuie folosit recursiunea. Deci, unde se folosește recursiunea? Un exemplu bun de când doriți să utilizați recursiunea este căutarea unui arbore binar.

Când datele sunt structurate într-un arbore binar, trebuie să mergeți pe multe căi pentru a căuta date. În fiecare punct al arborelui, trebuie să decideți dacă doriți să continuați să căutați în dreapta sau în stânga. Puteți salva ce parte a arborelui ați vizitat într-o variabilă, dar o funcție recursivă poate urmări în mod natural aceste informații.

Imaginează-ți că căutăm numărul șase din arborele de mai sus. Am putea face o funcție recursivă care caută arborele de la stânga la dreapta. Algoritmul ar arăta cam așa:

FUNCTION searchTree(branchToSearch) IF find 6 OR end of tree THEN RETURN result ELSE PROCESS branch CALL FUNCTION searchTree(left) CALL FUNCTION searchTree(right) END FUNCTION

În acest exemplu de pseudocod, algoritmul va căuta mai întâi partea stângă a arborelui. De fiecare dată când vizitează un număr nou, funcția este întreruptă și păstrată în memorie. Acest lucru ne permite să urmărim unde am fost.

Algoritmul va căuta întotdeauna în partea stângă cât poate mai întâi. odată ce ajunge la capătul arborelui, arborele de căutare (stânga) se va finaliza și va verifica partea dreaptă. Odată ce ambele părți sunt bifate, căutarea face backup pentru o ramură și continuă să verifice partea dreaptă.

Dacă algoritmii ar căuta în întregul arbore, ar face-o în ordinea:

2, 7, 2, 6, 5, 11, 5, 9 și 4

Vedeți dacă puteți urmări folosind pseudo-codul de mai sus.

Revizuirea recursiunii

Recursiunea este un subiect avansat. Va dura ceva timp pentru a înțelege și chiar mai mult pentru a deveni bun la codificare. Vă va ajuta dacă parcurgeți funcțiile recursive pas cu pas. S-ar putea chiar să vă ajute să stivuiți carduri index sau note post-it pe măsură ce parcurgeți o funcție când învățați să reprezentați fiecare apel de funcție.

Când scrieți o funcție recursivă, începeți prin a decide cum doriți să părăsiți funcția. Apoi, stabiliți cum să vă configurați bucla. Identificați ce informații trebuie trimise la următorul apel de funcție și ce trebuie returnate.

Cel mai bun mod de a învăța recursiunea este să o exersezi și să înveți din greșelile tale. Priviți o parte din vechiul cod și provocați-vă să rescrieți buclele ca funcții recursive. Probabil că nu vă va face codul mai eficient, dar va fi o practică bună.