2.3 Funcții recursive
Fiecare algoritm alocă în mod unic rezultatul datelor inițiale. Prin urmare, cu fiecare algoritm o anumită funcție este asociată în mod unic, pe care o calculează. Cu privire la clarificarea întrebării pentru care funcționează algoritmii și pentru care teoria funcțiilor recursive nu se bazează.
Principalul lucru este că întregul set de funcții studiate este construit dintr-un număr finit de funcții inițiale (bază) cu ajutorul unor operații simple, fezabilitatea efectivă a cărora este destul de evidentă. Operațiile asupra funcțiilor vor fi numite operatori.
2.3.1 Primitiv. funcții recursive
Functiile computerizate includ toate constantele, adica 0 și toate numerele naturale 1,2. Dar putem face cu 0 și cu funcția succesorală f (x) = x + 1 (x '). În plus, includem funcțiile de identitate în bază, desemnăm familia acestor funcții: Inm (x1, x2, Xn) = xm (m≤n). În caz contrar, se poate numi o funcție de introducere a variabilelor fictive. Definim o familie de operatori de suprapunere. pentru h (x1 .xm), gi (x1, xn), i = 1. m.
SNM (h, g1) = Gm ,? h (g1 (x1. Xn). Gm (x1. Xn)) = f (x1. Xn).
Operatorul primitiv de recursiune Rn
definește funcția f (n + 1) f în termenii funcției n-place g și (n + 2) - funcție similară astfel:
f (x1, xn, 0) = g (x1, xn)
f (x1 .xn, y + 1) = h (x1 .xn, y, f (x1 .xn, y))
Aceste formule sunt numite scheme de recursiune primitivă.
În cazul în care f este un loc, obținem următoarea reprezentare a schemei
f (0) = c
f (y + 1) = h (y, f (y))
Pentru a calcula f (x1, xn, k), avem nevoie de (k + 1) calcule conform schemei pentru y = 0,1,2. k.
O funcție se numește primitivă recursivă dacă poate fi obținută de la o constantă 0, o funcție x? și funcțiile Inm prin aplicarea unui număr finit de operatori de suprapunere și a schemelor primitive de recursiune.
1. Adunarea f + (x, y) = x + y - este primitiv recursiv
f + (x, 0) = x = I11 (x)
f + (x, y + 1) = f + (x, y) + 1 = (f + (x, y)
2. Înmulțirea fs (x, y) = xy este recursiv primitiv,
fs (x, 0) = 0
f (x, y + 1) = fs (x, y) + x = fs (x, fs (x, y))
3. Exponentierea fexp (x, y) = xy este recursivă primitivă
fexp (x, 0) = 1
fexp (x, y + 1) = xxy = fs (x, fexp (x, y))
Definim funcția x 0
Articole similare
Trimiteți-le prietenilor: