EditWYSIWYGAttachPrintable
r1 - 03 Oct 2005 - 15:46:44 - Luba ParmyonovaYou are here: TWiki >  Refaldevel Web > FuturePlans > RecIter

Перевод рекурсии в итерацию

Суть подхода такова:
если рекурсия выражает идею простого цикла можно использовать $iter. Так будет и эффективнее, и читабельней.

Правило эквивалентного преобразования Рефал-Плюс-программ.

Пусть имеем Рефал Плюс код:


$func F ARGS = e;

   F ARGS =
      {  ... тело, развилки, пути ... несколько (i = 1..N) веток ...
         ... которые заканчиваются так (рекурсия):
         
                = Е_left_i  E_right_i;
                
         ... или так (конец рекурсии, результат):

                = E_res_i;
         ...
     };

где Е* - выражения без вызовов функций, ARGS - жесткое образцовое.
Тогда эквивалентное итерационное определение функции:


   F ARGS =
      T ( ) ( ) ARGS $iter
      {  ... тело, развилки, пути ... несколько  (i = 1..N) веток ...
         ... которые заканчиваются так (продолжаем итерацию):
         
                = T (e.R_left Е_left_i) (E_right_i e.R_right) E_parms_i ;
                
         ... или так (конец итерации, результат):

                = F (e.R_left E_res_i e.R_right) ARGS;
         ...     
     } :: s.GoOn (e.R_left) (e.R_right) ARGS,
     s.GoOn : F
     = e.R_left;
Здесь s.GoOn, e.R_left, e.R_right - свежие (уникальные) переменные.

-- Luba Parmyonova - 03 Oct 2005

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r3 < r2 < r1 | More topic actions...
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback