Рекурсия по таблице О_о

[Masygreen]

Собственно сабж.. как сделать правильно??
Пример фейса ниже - смысл раскрутить формулу вычисления статьи затрат. Все бы хорошо но при рекурсии каждый раз сбрасывается _loop rcTable и получаем бесконечность ...
Надо как то заставить функцию ProcessSum открывать новый курсор в rcTable ...

Код: Выделить всё

interface MyInterface;
create view
  from rcTable
  ;

function ProcessSum(_prparent:comp;_prLivel:integer):double;
var _vSum:double;
{
 _loop   rcTable where ((_prparent==rcTable._Parent))
 { 
  _vSum := _vSum + ProcessSum(rcTable._Node,_prLivel+1);
 }
ProcessSum := _vSum;
}

HandleEvent
cmInit:
 {
   _loop VarTable
   {
     ProcessSum(VarTable._nRec,1);
  }
   CloseInterface(cmDefault);
   stop;
 }
 end; //HandleEvent
end.

[Masygreen]

походу сам себе ответил

Код: Выделить всё

external _loop

[Vik]

Не надо никаких externel, есть PushPos и PopPos

[n0where]

Не надо никаких externel, есть PushPos и PopPos

Разве это подходит под рекурсию?

PushPos и PopPos ведь можно использовать лишь для сохранения текущей позиции в буфер, причем только в 1 буфер. Рекурсия понимает под собой же вызов несколько раз процедуры, функции он сохранит только 2ой вызов (вложенный). а остальные (вложенные) заменит.

не прокатит же.

[Алексей]

зачем параметр prLivel:integer ? чтобы знать уровень вложенности? а зачем? вы же нигде это не используете.

я делал рекурсивные функции и у меня всё работало, правда она просто шла до дна и доставала значение последнего уровня.
глядя ваш код не совсем понимаю что хотите делать. суммировать какие-то значения или что?

[galover]

Push и PopPos будут работать 100%. Сам ими пользуюсь при рекурсиях. Работают они по принципу стека, т.е. запоминать можно более одной позиции. Вот в этой теме http://www.tyumbit.ru/gal_forum/viewtop ... 14&start=0 есть еще наглядный пример от Screw (внизу обсуждения) как заменить рекурсию (обход в глубину) на итерации (обход в ширину).

[Vik]

Разве это подходит под рекурсию?

Естественно, подходит. Если бы сам не использовал, не написал бы. И я в курсе, что такое рекурсия, не надо мне объяснять, как она работает. Почитайте в документации про эти процедуры)

[Masygreen]

зачем параметр prLivel:integer ? чтобы знать уровень вложенности? а зачем? вы же нигде это не используете.

я делал рекурсивные функции и у меня всё работало, правда она просто шла до дна и доставала значение последнего уровня.
глядя ваш код не совсем понимаю что хотите делать. суммировать какие-то значения или что?

надо надо .. только в другом месте - естественно функции гораздо больше .. это так пример краткий для понятия сути задачи...

[Masygreen]

Не надо никаких externel, есть PushPos и PopPos

подскажите чем PushPos и PopPos лучше externel?
это тоже первое что мне в голову пришло, но потом отбросит т.к. подумал, что как и в случае с _loop в каждом следующем вызове позиции будут сбрасываться....

[Masygreen]

Почитал про вариант с маркерами .. выгода я так понимаю только в скорости . Мне это не важно .. у меня таблица больше 100 элементов ни когда не будет ...

[Vik]

подскажите чем PushPos и PopPos лучше externel?

В общем, почему-то были необоснованные подозрения, что с external будет медленнее работать, но как только что выяснил, подозрения эти не оправдались. Написал на скорую руку небольшой тест:

Код: Выделить всё

Interface RecursionTest;
var
 _start : time;
 _stop  : time;
 times  : array[1..4] of time;

Create view
var
 vw_cPar: comp;
from
 Catalogs
,Catalogs Catalogs1
where
((
   vw_cPar == Catalogs1.cParent
))
;
function startTest(p_sTitle: string): void;
{
   _start := Cur_Time;
   WriteMessageLog(''#13'============ START : ' + p_sTitle + ' ============')
}
function stopTest(): time;
{
   _stop := Cur_Time;
   WriteMessageLog(''#13'============ END ============')
   NextVisual;
   result := Sub_Time(_stop, _start);
}
function recursion1(p_cPar: comp; p_sPad: string): void;
{
  _loop Catalogs where ((p_cPar == catalogs.cParent))
   {
      WriteMessageLog(p_sPad + catalogs.Name)
      PushPos(#Catalogs)
      recursion1(catalogs.Nrec, p_sPad + ' ')
      PopPos(#Catalogs)
   }
}
function recursion2(p_cPar: comp; p_sPad: string): void;
{
  external _loop Catalogs where ((p_cPar == catalogs.cParent))
   {
      WriteMessageLog(p_sPad + catalogs.Name)
      recursion2(catalogs.Nrec, p_sPad + ' ')
   }
}
function recursion3(p_cPar: comp; p_sPad: string): void;
var cCur: comp
{
  cCur := vw_cPar := p_cPar
  _loop Catalogs1
   {
      WriteMessageLog(p_sPad + catalogs1.Name)
      PushPos(#Catalogs1)
      recursion3(catalogs1.Nrec, p_sPad + ' ')
      vw_cPar := cCur;
      PopPos(#Catalogs1)
   }
}
function recursion4(p_cPar: comp; p_sPad: string): void;
var cCur: comp
{
  cCur := vw_cPar := p_cPar
  external _loop Catalogs1
   {
      WriteMessageLog(p_sPad + catalogs1.Name)
      recursion4(catalogs1.Nrec, p_sPad + ' ')
      vw_cPar := cCur;
   }
}
HandleEvent
  cmInit :
  {
     OpenMessageLog('e:\garbage\log\recursion.log', mfLog2Stream)
     var cStartNode: comp;

     //cStartNode := comp(471);
     cStartNode := comp(0);

     StartNewVisual(vtIndicatorVisual, vfTimer, 'Печать иерархии Catalogs', 4)

     startTest('Recursion1');
     recursion1(cStartNode, '');
     times[1] := stopTest();

     startTest('Recursion2');
     recursion2(cStartNode, '');
     times[2] := stopTest();

     startTest('Recursion3');
     recursion3(cStartNode, '');
     times[3] := stopTest();

     startTest('Recursion4');
     recursion4(cStartNode, '');
     times[4] := stopTest();

     var i : integer;

     for (i := 1; i <= 4; i++)
      {
        WriteMessageLog('Тест №' + i + ': ' + timeToStr(times[i], 'HH:MM:SS:SSS'))
      }

     CloseMessageLog ;
     StopVisual('',0);
  }
end;
End.  

Результаты трех прогонов получились такие:

Код: Выделить всё

Прогон 1
11:51:31 ¦ Тест №1: 00:00:06:29
11:51:31 ¦ Тест №2: 00:00:04:48
11:51:31 ¦ Тест №3: 00:00:05:95
11:51:31 ¦ Тест №4: 00:00:04:30
Прогон 2
11:52:16 ¦ Тест №1: 00:00:06:31
11:52:16 ¦ Тест №2: 00:00:04:50
11:52:16 ¦ Тест №3: 00:00:05:98
11:52:16 ¦ Тест №4: 00:00:04:22
Прогон 3
11:52:57 ¦ Тест №1: 00:00:06:36
11:52:57 ¦ Тест №2: 00:00:04:31
11:52:57 ¦ Тест №3: 00:00:05:94
11:52:57 ¦ Тест №4: 00:00:03:99

Так что зря я вас попутал, с external даже быстрее получается) А вод подцепки лучше все-таки во вьюху перенести.

[edward_K]

надо на своем выборе адреса попробовать - sterr все таки покруче будет catalogs.

[Vik]

Catalogs - первая таблица с иерархией и более-менее ощутимым числом записей, которая пришла в голову. Sterr у меня в три раза меньше.

[Den]

Обход без рекурсии и маркеров n-го узла деревянной таблицы :

Код: Выделить всё

Interface tree_example;
create view
var curNode, curParent:Comp;
  curnestlevel,nestLevel:Longint;
  from katpodr
      ,katpodr katpodr1 ;


Function GetNextNode(AParent:COMP; var ANode:COMP; var ANestLevel:Longint):boolean;
//Предполагается, что таблица ("TableAlias") упорядочена по CREC+.....
var curParent, curNode:COMP;
{

  Result:=False ;
  if ANode=0 {
                if GetFirst fastfirstrow katpodr where ((AParent==katpodr.cpodr)) =tsok
                {
                  ANode:=katpodr.NRec;
                  ANestLevel:=0;
                  Result:=True;
                  Exit;
                }
             }
  else 
    if GetFirst fastfirstrow katpodr where ((ANode==katpodr.cpodr))=tsok
    {
      ANode:=katpodr.NRec;
      ANestLevel:=ANestLevel+1;
      Result:=True;
      Exit;
    } 
    else
    {
      curNode:=ANode;
      curNestLevel:=ANestLevel;
      While (Result=False) do
      { 
        if GetFirst fastfirstrow katpodr where ((curNode==katpodr.nrec))<>tsOK
        {
          break;
        }
        curParent:=katpodr.cpodr;
        if GetNext fastfirstrow katpodr where ((curParent==katpodr.cpodr))=tsok
        {
          ANode:=katpodr.NRec;
          ANestLevel:=curNestLevel;
          Result:=True;
          break;
        }
        else
        {
          curNode:=curParent;
          curNestLevel:=curNestLevel-1;
          if (curNode = 0) OR (curNode = AParent) 
          {
            Result:=False;
            break;
          }
          else
          {
            Continue;
          }
        };
      }
      if (Result=False) {
        ANode:=0;
      }
    }
}


HandleEvent
CmInit: {
// n-ый просматриваемый узел
          curParent:=comp(16);
          curNode:=0;
          While (True = GetNextNode(curParent, curNode, nestLevel)) 
          do {
               if getfirst katpodr1 where ((curNode==nrec))=tsok {}
               logstrtofile('c:\debug\podrier.log',katpodr1.name+' NREC='+curNode+' на уровне '+nestLevel+' от родителя с NREC='+curParent);
             }
         }
end;
end.