Rekurzív függvény - logika - az elérhető minden
rekurzív függvények
Úgy véljük, csak a numerikus funkciókat, azaz a. E. Függvényargumentumok és amelynek értékeket a természetes számok halmaza N (N = 0,1,2, ...).
Ha a domain a funkció egybeesik a készlet, a függvény neve mindenütt meghatározott, vagy - részben megadott.
f (x, y) = x + y - függvény mindenütt,
f (x, y) = x-y - részlegesen meghatározott funkciója, azaz, hogy a meghatározott csak ...
Rekurzív definíció funkciók - ez a meghatározás, ahol a függvény értéke érv az adatok értékei határozzák meg az azonos funkciót az egyszerűbb értékeit érvek vagy több egyszerűbb funkciókat.
1. Fibonacci számok (1, 1, 2, 3, 5, 8, ...) egy számsorozat f (n), ahol f (0) = 1, f (1) = 1, f (n + 2) = f (n) + f (n + 1).
2. A faktoriális (n! = 1 * 2 * 3 * ... * n) f (0) = 1, f (n + 1) = f (n) * (n + 1).
Rekurzív függvények alapulnak három primitív (nyilván világosan érthetővé és alkalmazhatóvá) funkciókat. Ezek is nevezik egysejtűek.
1. S (x) = x + 1 - ismétlés funkció.
Példák. S (0) = 1, S (1) = 2, S (-5) - nem határoztuk meg.
2. G (x) = 0 - nulla értékű függvény;
Példák: G (0) = 0, D (1) = 0, és G (-5) - nem határoztuk meg.
3. Im (x1, x2, ..., xn) = xm, (m = 1,2, ... n) - tervezési funkció (kiválasztási argumentum).
A primitív funkciók elvégzésére különféle manipulációk segítségével három szolgáltató: szuperpozíció primitív rekurzió, illetve minimalizálásával.
1. szuperpozíció üzemeltető (szubsztitúció).
Legyen f - m-hely funkciót, g1, ... GM - N-a helyi műveletek a beállított N. szuperpozíció üzemeltető S hozzárendeli a műveletek az f és g1, ... GM N-a helyi h függvény.
1) A szuperpozíció operátor, akkor kap minden állandó.
S (S ... (O (x)) ...) = 0 + n, ahol n a mellékletek számát alábbi funkciók.
2) A készítmény üzemeltető végezhet műszak állandó n.
2. Az üzemeltető a primitív rekurzió
Minden üzemeltető R (n + 2) -place műveletek F- és N-a helyi műveletek hozzárendeli a g (n + 1) férőhelyes művelet h = R (f, g), kielégíti a következő séma szerint:
Az n = 0 primitív rekurzió program a formája:
, ahol a - állandó
Példa: Számítsuk ki a faktoriális segítségével primitív rekurzió operátor a következő lesz.
Reakcióvázlat primitív formák rekurzió folyamat függvényt h csoport, amelyben egy nulla lépésben használ g függvény, és minden egyes egymást követő lépésben a értéke az f függvény érvek szám y előző lépésben, és az értékét a függvény H, kiszámított az előző lépésben.
A funkció úgynevezett primitív rekurzív (PRF), ha lehet beszerezni a kezdeti funkciókat a szuperpozíció az üzemeltető vagy az üzemeltető a primitív rekurzió.
1) - primitív rekurzív függvény.
A rendszer a primitív rekurzió:
2) - primitív rekurzív függvény.
3. minimalizálása érdekében az üzemeltető (az üzemeltető)
, ahol y - a kiválasztott változók.
Work-üzemeltető a következőképpen írható le. Lekötött y változó, majd rögzíteni a többi változó. Az y érték növekedése egymás, kezdve 0. Az érték-operátor lesz az érték, amelynél a függvény először alkalmazzák 0.
Ha a funkció nincs bekapcsolva, 0 vagy negatív érték, az érték nem definiált operátor.
Mi fix x = 1 és y fog változni.
A f (x1, x2, ..., xn) egy részlegesen rekurzív (CHRF) ha lehet beszerezni a kezdeti funkciókat véges számú használ szuperpozíció, primitív rekurzió és minimalizálása.
f (x, y) = x-y - .. részleges, vagyis nem kell meghatározni, ha x Tulajdonságok csonka különbség. Rekurzív függvény primitív, vagyis a rendszer primitív rekurzió ..: Így. lehet beszerezni az eredeti funkciók o (x) és Im (x1, ... xn) egy egyszerű rekurzív operátor R. A program keretében a primitív rekurzió Így. funkció segítségével kapott működését a primitív funkcióinak rekurzió és h (x, y, z) =. Ezért, az f (x, y) = X-Y jelentése egy részlegesen rekurzív függvény. Mindenütt meghatározott részleges rekurzív függvény rekurzív (RUF). Algoritmikus problémák tipikus helyzet, amikor meg akarja találni egy algoritmus kiszámítja a numerikus függvény f (x1, ... xn). Numerikus funkció, amelynek értékeit ki lehet számítani egy algoritmus, az úgynevezett kiszámítható függvényt. Ez a koncepció az intuitív, t. Hogy. Az intuitív fogalma egy algoritmus. Az f (x1, ... xn) ténylegesen kiszámítható, ha van olyan algoritmus, amely lehet használni, hogy megtalálja az f (k1, ... kn), ha ismert k1, ... kn. Church tézisét. Bármilyen hatékonyan számolható függvény részleges rekurzív függvény. Az Egyház tézis megfogalmazása tartalmazza a fogalom tényleges kiszámíthatóság. Ezért nem lehet sem megerősíteni, sem cáfolni matematikai értelemben. Részleges rekurzív - pontosítás a fogalom számolható függvény. Ezt fel lehet használni, hogy finomítsa vagy cáfolja kiszámíthatóság. Bármely részleges rekurzív függvény kiszámítható Turing és fordítva.
Kapcsolódó cikkek