Вопрос 10. Привести пример программы, использующий восходящую рекурсию для операции со списками.


Добавил:DMT
Дата создания:30 декабря 2007, 19:23
Дата обновления:30 декабря 2007, 19:23
Просмотров:8833 последний позавчера, 17:12
Комментариев: 2
Вопрос 10. Привести пример программы, использующий восходящую рекурсию для операции со списками.
up

Комментарии для "Вопрос 10. Привести пример программы, использующий восходящую рекурсию для операции со списками."


Пользователь: DMT
Сообщений: 123
Статус: Программист
Зарегистрирован:
18 октября 2007, 2:35
Был:13 ноября 2017, 4:54
DMT
smsup
Дата: 4 января 2008, 16:30 Сообщение № 1
Восходящая рекурсия - промежуточные результаты вычисляются на некоторой стадии рекурсии, так что ответ строится постепенно и передается в виде параметра рабочей памяти до тех пор. пока не будет достигнута некоторая ( терминальная ) ситуация. К этому моменту ответ уже готов, и нужно передать его вызывающей функции верхнего уровня.

Пример 1
Код на Lisp
  1. /*Вычисление длины списка с помощью восходящей рекурсии */
  2. domains
  3. sl = symbol*
  4. nl = integer*
  5. predicates
  6. list_len ( sl, integer )
  7. list_len ( nl, integer )
  8. l_l ( sl, integer, integer )
  9. l_l ( nl, integer, integer )
  10. clаuses
  11. list_len ( X, N ) :- l_l ( X, N, 0 ).
  12. l_l ( [ ], N, N ).
  13. l_l ( [ _ | R ], N, N1 ) :- N2 = N1 + 1, l_l ( R, N, N2 ).
При использовании обязательна ссылка на http://DMTSoft.ru

В некоторых случаях, при использовании рекурсии, результат вычисляется по-разному, следовательно, он зависит от выбора вида рекурсивной функции.

Пример 2:
Код на Lisp
  1. /*Копирование списка с помощью разных видов рекурсии */
  2. // список копируется в обратном порядке – рекурсия восходящая.
  3. ucopy ( W, S ) : - cop ( W, [ ] ).
  4. cop ( [ ], S ).
  5. cop ( [ X | Y ], [ X | _ ] ) : - cop ( Y, S ).
При использовании обязательна ссылка на http://DMTSoft.ru
Пользователь: kate
Сообщений: 9
Статус: Незримый
Зарегистрирован:
4 января 2008, 14:05
Был:28 января 2008, 21:05
kate
smsup
Дата: 8 января 2008, 13:22 Сообщение № 2
sort (SLIST,SLIST) %предикат быстрой сортировки
• 1-й аргумент – список строк, который требуется отсортировать;
• 2-й аргумент – отсортированный список строк (результат).
Данное правило использует восходящую рекурсию для сортировки списка(1-й аргумент) и перемещения отсортированного списка в результирующий список(2-й аргумент).

div2(STRING,SLIST,SLIST,SLIST)%предикат разбиения списка
• 1-й аргумент – голова списка X;
• 2-й аргумент – хвост;
• 3-й аргумент – список элементов меньше Х;
• 4-й аргумент – список элементов больше Х.

link(SLIST,SLIST,SLIST) %предикат конкатенации списков
• 1-й аргумент – 1 список;
• 2-й аргумент – 2 список;
• 3-й аргумент – результат конкатенации списков 1 и 2.


Код на Lisp
  1. PREDICATES
  2. sort(SLIST,SLIST)
  3. div2(STRING,SLIST,SLIST,SLIST)
  4. link(SLIST,SLIST,SLIST)
  5. CLAUSES
  6. /*сортировка списка(Быстрая сортировка)*/
  7. div2(_,[],[],[]).
  8. div2(X,[Y|TAIL], [Y|S],L):-X>Y,!,div2(X,TAIL,S,L).
  9. div2(X,[Y|TAIL], S,[Y|L]):-div2(X,TAIL,S,L).
  10. link([],L,L).
  11. link([X|L1],L2,[X|L3]):-link(L1,L2,L3).
  12. sort([],[]).
  13. sort([X|TAIL],SORTLIST) :-div2(X, TAIL, S, L),
  14. sort(S, SORTS),
  15. sort(L, SORTL),
  16. link(SORTS,[X|SORTL],SORTLIST).
При использовании обязательна ссылка на http://DMTSoft.ru