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


Добавил:DMT
Дата создания:30 декабря 2007, 19:23
Дата обновления:30 декабря 2007, 19:23
Просмотров:9500 последний вчера, 22:58
Комментариев: 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.     
  6. predicates    
  7. list_len ( sl, integer )    
  8. list_len ( nl, integer )    
  9. l_l ( sl, integer, integer )  
  10. l_l ( nl, integer, integer )  
  11.     
  12. clаuses    
  13. list_len ( X, N ) :- l_l ( X, N, 0 ).  
  14. l_l ( [ ], N, N ).  
  15. l_l ( [ _ | R ], N, N1 ) :- N2 = N1 + 1, l_l ( R, N, N2 ).
При использовании обязательна ссылка на http://DMTSoft.ru

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

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