Lazarus

Programming => General => Topic started by: CandyMan30 on December 08, 2022, 07:27:10 pm

Title: How to get rid of the recursion?
Post by: CandyMan30 on December 08, 2022, 07:27:10 pm

How to get rid of the recursion in the example below?
I could use a list, but how?

procedure tOptomizer.DoExpression( var CodeTree: pCodeTree);
  begin
    if Assigned( CodeTree) then
      begin
        DoExpression( CodeTree^.Left);
        DoExpression( CodeTree^.Right);
        case CodeTree^.Node.CodeType of
...

Title: Re: How to get rid of the recursion?
Post by: MarkMLl on December 08, 2022, 08:05:25 pm

Excessive fondness of recursion is something that often falls into my "Computer Science Crap" category. However unless you have very specific runtime requirements I suggest sticking with what you've got in the current scenario... albeit with careful depth etc. checking if you suspect that you'll be up against resource limitations.

In any event, you will need to consider whether an attempted conversion to an operations list does actually reduce the resource usage: recursion in a language with support for it can end up being very efficient.

MarkMLl

Title: Re: How to get rid of the recursion?
Post by: PascalDragon on December 08, 2022, 09:50:20 pm

Quote from: CandyMan30 on December 08, 2022, 07:27:10 pm

How to get rid of the recursion in the example below?
I could use a list, but how?
Code: Pascal [Select][+][-]
procedure tOptomizer.DoExpression( var CodeTree: pCodeTree);
begin
if Assigned( CodeTree) then
begin
DoExpression( CodeTree^.Left);
DoExpression( CodeTree^.Right);
case CodeTree^.Node.CodeType of
...

What you're doing here is a depth-first search (https://en.wikipedia.org/wiki/Depth-first_search#Pseudocode) of a node tree. So you can do this with a loop and a stack (check the pseudo code in the linked article) though you might need to be careful when you do indeed change the CodeTree variable as the var suggests.