Intellektual tizimlar

1.2.4.2. Rekursivnыye funksii: opredeleniye i ispolneniye.

Opredeleniya mogut bыt rekursivnы. Kak pravilo rekursivnoye primeneniye funksiy doljno bыt opredeleno v komplekte s nerekursivnыmi vetvyami prosessa. Osnovnoye prednaznacheniye uslovnыx vыrajeniy - rekursivnыye opredeleniya funksiy.
Dlya primera rassmotrim funksiyu, vыbirayuщuyu v spiske samыy levыy atom:
(DEFUN Leveyshiy (x)
(COND ((ATOM x) x)
(T (Leveyshiy (CAR x))) ))
Yesli x yavlyayetsya atomom, to on i yavlyayetsya rezultatom, inache funksiyu "Leveyshiy" sleduyet primenit k pervomu elementu znacheniya x, kotoroye poluchayetsya v rezultate vыchisleniya formulы (CAR x). Na sostavnыx x budet vыpolnyatsya vtoraya vetv spesialnoy funksii COND, vыbirayemaya po tojdestvenno istinnomu znacheniyu vstroyennoy konstantы T.
Opredeleniye funksii "Leveyshiy" rekursivno. Eta funksiya deystvitelno rabotayet v terminax samoy sebya. Vajno, chto dlya lyubogo S-vыrajeniya suщyestvuyet nekotoroye chislo primeneniy funksii CAR, posle kotorogo iz etogo S-vыrajeniya obyazatelno vыdelitsya kakoy-nibud atom, sledovatelno prosess vыchisleniya funksii vsegda opredelen, determinirovan, zavershitsya za konechnoye chislo shagov. Mojno skazat, chto dlya opredelennosti rekursivnoy funksii sleduyet formulirovat usloviye yeye zaversheniya.
Nekotorыye opredeleniya funksiy mogut bыt xorosho opredelenы na odnix argumentax, no zasiklivatsya na drugix, podobno tradisionnomu opredeleniyu faktoriala pri popыtke yego primenit k otrisatelnыm chislam. Rezultat mojet vыglyadet kak ischeznoveniye svobodnoy pamyati ili slishkom dolgiy schet bez vidimogo progressa. Takiye funksii nazыvayut chastichnыmi. Ix opredeleniya doljnы vklyuchat v sebya vetvleniya dlya proverki argumentov na prinadlejnost fakticheskoy oblasti opredeleniya funksii - dinamicheskiy kontrol. Uslovnыye vыrajeniya ne meneye udobnы i dlya chislennыx
Programma 1. Faktorial neotrisatelnogo chisla.
(DEFUN Faktorial (LAMBDA (N)
(COND ((= N 0 ) 1 )
(T ( * N (Faktorial (- N 1 ))) )
) ) )