Recurgerea este una dintre principalele metode de programare. Funcțiile recursive sunt funcții care depind de ele înseși. Când am analizat automatele, am vorbit despre funcțiile tranzițiilor, care în momentul ulterior al automatonului depind de valorile lor din clipa precedentă. Acesta este modul în care este implementată memoria automată. În teoria funcțiilor recursive care istoric considerate primele concepte formalizare algoritm se aplică cuvinte de numerotare în numere naturale alfabet arbitrare (N), precum și orice algoritm reduce la calcularea unei funcții la valori întregi ale argumentelor [22].
Funcția este calculabil dacă există un algoritm, care este, pas cu pas procedura „de la simplu la complex“, care este de intrare set de variabile calculează valoarea funcției, în cazul în care setul de intrare aparține domeniului funcției, și afișează un mesaj care setul de intrare nu aparține domeniului de definire funcție.
Funcția este semi-computabilă dacă, atunci când specificăm un set de intrare care nu aparține domeniului definiției funcției, algoritmul nu termină lucrarea ("buclă"). Teoria calculului a fost dezvoltată de A. Church. Ideea a fost similară cu studiul problemei noastre de funcții funcționale de comutare completitudine: selectați funcțiile calculabile elementare (care sunt „intuitiv calculabila“) - care este baza și oferă un mijloc de a ieși din aceste funcții calculabile elementare funcții mai complexe într-un număr finit de etape (ca principiul superpoziției în comutație teorie funcţii). Funcțiile astfel obținute vor fi de asemenea computerizate.
Astfel de funcții elementare sunt:
1) S (x) = x + 1, (N N), funcția succesiune (indică următorul număr natural);
2) 0 (x) = 0, constanta zero;
3) Im (x1 x2 ... xn) = xm - funcția de proiecție, care are ca rezultat selectarea m-lea n argumente.
Pentru a obține de la alte funcții semi-computerizate alte funcții într-un număr finit de etape, s-au propus așa-numiți operatori.
Primul dintre aceștia este operatorul de suprapunere cunoscut de noi; înlocuire în funcții funcționale în locul variabilelor. Aceasta crește dimensiunea funcției.
Cel de-al doilea operator este operatorul primitiv de recursiune.
Luați în considerare exemplul specificării seriei numerelor Fibonacci 1,1,2,3,5,8,13,21, ... folosind operatorul primitiv de recursiune:
Aici sunt indicate două valori inițiale ale funcției f (0), f (1) și principiul formării valorii ulterioare. Spre deosebire de funcțiile de tranziție ale automatului, nu este timpul automat, ci pasul de calcul n, adică, valoarea funcției la o anumită etapă diferită de zero și prima este egală cu suma valorilor funcției din cele două etape anterioare.
Luați în considerare un alt exemplu de utilizare a operatorului primitiv de recursiune:
f (0) = 1, f (1) = f (0) x 1 = 1, f (2)
Deci, am setat funcția factorială: x!
Funcțiile obținute de la elementar, printr-un număr finit de aplicații ale operatorilor de suprapunere și recursiune primitivă, se numesc primitiv-recursivi. O recursivitate mai complexă este de asemenea considerată, de exemplu, multiplă, în funcție de mai multe variabile simultan [19].
Sunt toate funcțiile primitiv-recursive? Se poate demonstra că mulțimea tuturor funcțiilor, cum ar fi un singur număr întreg N N, unde N - mulțimea numerelor naturale, nenumărabile, cu atât mai mult acest lucru este valabil pentru tipul N n N. Funcția fiecărei funcții recursive primitive are o descriere finită, adică, este dat de un cuvânt finit într-un anumit alfabet fixat pentru toate funcțiile [19]. Mulțimea tuturor cuvintelor finite numărabile, funcțiile recursive totuși primitive forma nu mai mult subset nenumărat numărabilă din multitudinea de funcții de tip N n N. Mai mult, se pare că nu toate funcțiile calculabile pot fi descrise ca recursivă primitive.
Cel de-al treilea operator este operatorul de minimizare m. care vă permite să intrați în calcul pentru a găsi valoarea dorită.
Amintiți-vă că x1. x2 sunt numere naturale. Astfel de funcții sunt numite parțial recursive, adică nu sunt definite complet, spre deosebire de cele recursive primitive definite în întregime. În conformitate cu teza bisericii, o funcție este semi-calculată dacă și numai dacă este parțial recursivă.
Există funcții non-computable în care relația dintre cantitățile de intrare și de ieșire este atât de complexă încât este imposibil să specificăm un proces strict definit pas cu pas de transformare a datelor originale într-un rezultat [36], adică Este imposibil să se construiască un algoritm pentru rezolvarea problemei corespunzătoare.
Funcțiile recursive reprezintă baza programării funcționale. Un exemplu de limbă de programare funcțională este limba LISP, dezvoltată în 1960. D. McCarthy. Aceasta este una dintre primele limbi de procesare a datelor în formă simbolică (LISP, de la procesarea LISt - prelucrarea listelor). Una dintre cele mai importante caracteristici ale limbajului LISP este că datele, programele și chiar limba în sine sunt doar liste de caractere în paranteze. Această structură vă permite să scrieți programe sau subrutine care se pot adresa ei înșiși [37].
În LISP, se utilizează o formă de prefix:
Definirea funcțiilor și calcularea lor în limba se bazează pe calculul așa-numit lambda introdus în 1931. Prin Biserică:
unde # 955; - definirea funcției, x1, ..., xn - parametrii formali (lista lambda), fn - corpul funcției.
Recursurile sunt de asemenea prezente în limbile programării structurale.
Luați în considerare un exemplu de rezolvare a unei probleme Pascal folosind recursivitatea [3].
PROBLEMĂ h o. Există o definiție recursivă a factorială:
Aici, n este non-negativ. Scrieți această funcție în Pascal.
Soluția. Prima linie a definiției indică în mod explicit cum se calculează factorul dacă argumentul este zero sau unul. În orice alt caz, pentru a calcula n! este necesar să se calculeze valoarea anterioară (n-1)! și se înmulțește cu n. O valoare descrescătoare asigură că în cele din urmă va fi nevoie să găsiți 1! sau 0. care sunt calculate direct.
încep dacă (i = 1) sau (i = 0)
începe scrie ('Introduceți valoarea dorită a n');
writeln ('Factorial', n, 'este egal', fapt (n));
Rețineți că, în timp ce algoritmul auxiliar funcționează, algoritmul principal este suspendat. Atunci când este apelată o nouă copie a algoritmului recursiv, spațiul pentru toate variabilele declarate în el este alocat din nou, cu variabilele celorlalte copii indisponibile. Când ștergeți o copie a algoritmului recursiv, toate variabilele sale sunt, de asemenea, șterse din memorie. Copia anterioară a algoritmului recursiv este activată, iar variabilele sale devin disponibile. Fie ca este necesar să se calculeze 4. Algoritmul principal: n = 4 este introdus, provocarea este realitatea (4). Algoritmul principal este suspendat, el este numit și fapta (4) rulează: 4<>1 și 4<>0, deci fact: = fact (3) * 4. Funcția de lucru este suspendată, este apelată și fapta (3) se execută: 3<>1 și 3<>0, deci fapt: = fapt (2) * 3. În prezent, există două copii ale funcției fact în memoria calculatorului. Fapte numite și difuzate (2): 2<>1 și 2<>0, deci fact: = fact (1) * 2. Există deja trei copii ale funcției fact în memoria calculatorului și se cheamă a patra. Faptul (1) este numit și funcționează: 1 = 1, deci fapta (1) = 1. Lucrarea acestei funcții este finalizată, lucrarea de fapt (2) continuă. fapt (2): = fapt (1) * 2 = 1 * 2 = 2. Funcția acestei funcții este de asemenea finalizată, iar funcția funcțională (3) continuă să funcționeze. fapt (3): = fapt (2) * 3 = 2 * 3 = 6. Funcția acestei funcții este finalizată, iar funcția (4) continuă să funcționeze. fapt (4): = fapt (3) * 4 = 6 * 4 = 24. După aceea, controlul este transferat în programul principal și răspunsul este tipărit: "Factorial 4 este 24".
Articole similare
Trimiteți-le prietenilor: