Coada recursivitate în timpanică
În acest post voi vorbi despre fiche interesant de programare functionala - pe recursivitate coada. Dar, mai întâi, să ne amintim ce recursivitatea generală. Deci, recursivitate - o descriere a unui anumit obiect, care este o parte integrantă din el însuși. De exemplu, o expresie matematică poate conține operanzi numerice, aritmetică și alte expresii matematice.
În această lucrare ne confruntăm cu funcții recursive. Pentru a găsi valoarea unei astfel de funcții pentru un anumit set de parametri de intrare necesari pentru a găsi valoarea acestei funcții pentru un set diferit de parametri de intrare. Cu alte cuvinte, o funcție care se numește. Cel mai faimos exemplu de recursivitate este factorial (așa spun majoritatea manualelor cu privire la programarea) si numerele lui Fibonacci. Uita de factorialele și să vedem cum arată punerea în aplicare a numerelor Fibonacci in Java:
După cum se poate observa din exemplul, înainte de o valoare returnată dintr-un apel de funcție are loc două din aceeași funcție, dar cu valori diferite.
recursivitate coada
Acum, înapoi la coada-recursiv. Recursivitatea este coada, în cazul în care apelul este funcția recursiv va fi ultima operație înainte de a reveni. Să ne rescrie exemplul anterior folosind recursivitate coada:
API-ul clasei sa schimbat: avem încă o metodă care returnează numărul Fibonacci n-lea. De asemenea, avem o nouă metodă fibIter privată. care cuprinde o recursivitate coadă. Foarte des, pentru punerea sa în aplicare, o metodă de ajutor care ia starea înainte de următoarea iterație a recurență. Cu această recursivitate coada poate fi reprezentat ca un ciclu:
Acest cod arată groaznic și există multe locuri unde puteți merge prost, asa ca de multe ori favorizat funcțiile recursive din cauza scurtării și lizibilitatea acestora.
Hai să verificăm funcțiile noastre în luptă și conta element de 10.000-lea al secvenței. Spre nefericirea noastră, cele două metode - și FIB. și fibWithTailRec - arunca java.lang.StackOverflowError. Acest lucru sugerează că utilizarea recursivitatii în Java pentru ușor. Și nu uitați despre metoda de a folosi o buclă :)
Scala de salvare
Și ceea ce ei cred despre recursie alte limbi JVM? Să vedem cum stau lucrurile la Scala cu funcții recursive și rescrie atât punerea în aplicare a codului recursiv, avand in vedere numerele lui Fibonacci. Să încercăm să facem cele mai similare în implementarea aceleași funcții:
Și acum, încă o dată contoriza numărul Fibonacci numarul 10.000, dar la Scala. Se pare că versiunea de coada-recursiv făcut față cu succes sarcina. Care este diferența dintre aproape „același“ cod în Java și Scala. Să ne uităm la codul de octet al acestor metode (javap -c) și a verifica ceea ce este, de fapt ar trebui să facem compilatoare:
Scala compilatorul a dat seama că această recursivitate coadă, și se întinde o functie recursiva în ciclu, care, după cum am văzut mai devreme, pentru a scrie, nu atât de frumos.
Lumea nu va mai fi la fel din nou
Deci, noi știm deja recursivitate coada cum abrupt. Este timpul pentru a aplica aceste cunoștințe. mondială PO, nici un program nu este completă fără o listă. Încercați să realizeze în mod independent, convoluția - una dintre operațiile de bază de pe listă (Scala lui ne oferă două versiuni - pe stânga și dreapta) (El este, de asemenea, cunoscut sub numele de pliul reduce.):
După cum puteți vedea, ambele funcții sunt recursive, dar, de groază de orori, foldRight nu are nici o recursivitate coadă, așa că ne confruntăm cu o depășire de stivă. Există o soluție destul de simplă, care este, desigur, necesită costuri suplimentare, dar nu inrautati complexitatea algoritmului tau. Scriem dreptul prin convoluție convoluție stânga:
Dacă noi nu credem va fi funcția noastră este optimizată sau nu, și am fi foarte mult fi dorit, puteți utiliza @tailrec adnotată. O opinie destul de comună este că o echipă de compilator pentru a face recursivitate coadă în metoda. Dar nu este (mai ales că o astfel de conversie nu este întotdeauna posibil). Se face doar să verifice dacă ea a marcat recursivitate caracteristica coadă, și, dacă nu, va exista o eroare de compilare. Motivele pentru acest lucru un pic și sunt ușor de verificat:
- acest lucru nu este metoda finală, ceea ce înseamnă că poate fi suprascrisă în subclase
- metoda nu se produce, și anume nu este recursiv
- nu e coadă de recurență.
