Recent

Author Topic: How to get rid of the recursion?  (Read 253 times)

CandyMan30

  • New Member
  • *
  • Posts: 12
How to get rid of the recursion?
« 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][+][-]
  1. procedure tOptomizer.DoExpression( var CodeTree: pCodeTree);
  2.   begin
  3.     if Assigned( CodeTree) then
  4.       begin
  5.         DoExpression( CodeTree^.Left);
  6.         DoExpression( CodeTree^.Right);
  7.         case CodeTree^.Node.CodeType of
  8. ...

MarkMLl

  • Hero Member
  • *****
  • Posts: 5866
Re: How to get rid of the recursion?
« Reply #1 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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 4880
  • Compiler Developer
Re: How to get rid of the recursion?
« Reply #2 on: December 08, 2022, 09:50:20 pm »
How to get rid of the recursion in the example below?
I could use a list, but how?
Code: Pascal  [Select][+][-]
  1. procedure tOptomizer.DoExpression( var CodeTree: pCodeTree);
  2.   begin
  3.     if Assigned( CodeTree) then
  4.       begin
  5.         DoExpression( CodeTree^.Left);
  6.         DoExpression( CodeTree^.Right);
  7.         case CodeTree^.Node.CodeType of
  8. ...

What you're doing here is a depth-first search 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.

 

TinyPortal © 2005-2018