Прологтағы Рекурсия Өзін-өзі шақыру механизмін пайдалану

Тізімдер рекурсивті құрылымдар. Жоғарыдағы келтірілген қызметкерлер жайлы мәліметтері бар мысалында қарапайым дерек өрістерінің жазбаларына қатынауды іске асыратын nth және list функцияларын пайдаландық. Қызметкерлер жайлы жазбалардың барлығының тұрақты ұзындығы болғандықтан (үш элементтен тұрады) осы аталған екі функцияны қарастыру жеткілікті болады. Бірақ ұзындығы тұрақсыз болатын жазбалар үшін, бұл функциялар аз. Бұндай операцияны орындау үшін тізімді итеративті немесе рикурсивті түрде сканерлеу мүмкіндігі болуы қажет. Яғни белгілі бір шарт орындалғаннан кейін (қажет жазба жазылған соң) немесе тізімді толық қарап шыққан соң операциялар орындалуы керек. Енді тізімдерді өңдеуде рекурсия қолданылатын функцияларды анықтайтын тізімдермен жұмыс істейтін операцияларды қарастырайық. Тізім компоненталарына қатынауды іске асыру функцияларына car және cdr жатады. 1-ші бір аргументтен, тәуелді және өзі де тізім, 1-ші элементті қайтарады. Cdr – функциясы да бір аргументтен тәуелді, ал тізімнің бірінші элементін алып тастағаннан кейінгі тізімді қайтарады. Мысалы:

> (car '(а b с)) ; тізім квотталған

а

> (cdr '(а b с)) (b с)

(а b)

((с d))

b

car және cdr функциялары тізімдік құрылымдармен рекурсивті түрде жұмыс істеуге негізделген тізімнің әр элементіне арналған операциялар келесі түрде орындалады.

2. Қарсы жағдайда тізім элементі өңделіп, қадам жолы тізімнің келесі элементіне өтеді.

Осы схема бойынша тізіммен жұмыс істейтін көптеген функцияларды анықтауға болады. Мысалы Common LISP(CL) –тілі кейбір S-өрнегінің тізімге жатуын анықтайтын member предикатын, тізім ұзындығын табатын length предикатын өз құрамында ұстайды. Осы функциялардың басқа версияларын қарап өтелік, яғни ол my-member функциясы екі аргументтен тұрады, кез-келген S-өрнегінен және my-list тізімінен. Егер S-өрнегі my-list тізімінің элементі болмаса, онда ол nil-қайтаруы керек. Қарсы жағдайда функция S-өрнегін 1-ші элемент есебінде ала отырып, тізімді айналдыра береді.

defun my-member (element my-list)

(cond ((null my-list) nil) ;элемент тізім мүшесі бола алмайды

((equal element (car my-list)) my-list)

'элемент табылды

(t (my-member element (cdr my-list))))) ;рекурсия қадамы

Мысалы my-member функциясын пайдаланып көрейік.

(my-member 4 '(1 2 3 4 5 б)) 5 б)

(my-member 5 ' (а b с d) ) Ф:

Осыған ұқсас length және nth функцияларының версияларын анықтаймыз..

defun my-length (my-list)

(cond ((null my-list) 0)

(t (+ (my-length (cdr my-list)) 1)))) e

defun my-nth (n my-list)

(cond ((zerop n) (car my-list)) ; zerop функция сы тексереді ; барлық аргументтің 0-ге тең екенін

(t (my-nth (-n 1) (cdr my-list)))))

Сar және cdr-ден басқа Лисп тілінде тізімдерді құратын функциялар жиынтығы бар. Соның бірі- list. Ол кез-келген мөлшердегі аргументтері бар өрнек болып табылады. Функция оларды бағалайды да нәтижелер тізімінқайтарады. Тізімдердің қарапайым конструкторы болып cons-функциясы табылады. Бұл функцияның параметрлері ретінде екі S-өрнегі жүреді. Бұл параметрлер бағаланады да, нәтиже ретінде тізім қайтарылады. Тізімнің 1-ші элементі ретінде 1-ші аргумент мәні, ал тізім құйрығы ретінде 2-ші аргумент мәні жүреді.

~ 2 3 4)

(cons '(а b) '(с d е))

(а b) c d е)

Сons-функциясын car және cdr функциясының кері түрлендіруі деп есептеуге болады, өйткені car функциясын cdr функциясының қайтару мәніне қолдану нәтижесінде cons-функциясының 1-ші аргументін аламыз. Осыған ұқсас cdr функциясын cons қайтару формасына қолдану нәтижесінде осы форманың 2-ші аргументін аламыз.

> (car (cons 1 '(2 3 4)))

1

> (cdr (cons 1 '(2 3 4)))

Сons-функциясын пайдалану мысалын қарастырайық. Ол үшін filter-negatives функциясын анықтайық. Оның параметрі есебінде сандық тізім жүреді. Бұл функция тізімдегі барлық теріс мәндерді жояды. Filter-negatives функциясы тізім элементтерін рекурсивті түрде тексереді. Егер 1-ші элемент теріс болса, онда ол алынып тасталады да, функция тізім құйрығының теріс элементтері сұрыптау нәтижесін қайтарады. Тізім құйрығы cdr функциясы арқылы анықталады. Егер тізімнің 1-ші элементі оң болса, онда ол сұрыпталған құйрықтағы теріс сандар нәтижесіне қосылады.

((defun filter-negatives (number-list)

(cond ((null number-list) nil)

;условие останова

( (plusp (саг пшпЬет-list)) (cons (саг пшпЬег-list)

(filter-negatives

(cdr number-list))))

(t (filter-negatives (cdr number-list)))))

Осы функцияның шақырылу мысалы.

> (filter-negatives '(1 -1 2 -2 3 -4))

(1 2 3)

(cond ((null list1) list2)

(t (cons (car listl) (my-append (cdr list1) list2)))))

Осы функциялардың шақыруын проиллюстрируем .

> (my-append ' (1 2 3) ' (4 5 б) )

(1 2 3 4 5 б)

My-append, my-length, my-member функциясын анықтау осы жоғарыда аталған рекурсивті схемаға ұқсас жүреді. Әр анықтауда тізімдегі элементті алып тастау үшін cdr функциясы қолданылады. Бұл қысқартылған тізімді рекурсивті түрде шақыру мүмкіндігін қамтамасыз етеді. Егер тізім бос болса, рекурсия аяқталады. Рекурсия процессі кезінде cons функциясы шешіледі де қайтадан қарап отырады. Бұл схеманы әдетте cdr - рекурсиясы (cdr-recursion) деп немесе құйрықтық рекурсия (tail resursion) деп атайды. Өйткені cdr функциясы тізім құйрығын алу мүмкіндігін береді.