flat assembler
Message board for the users of flat assembler.

Index > High Level Languages > How to get rid of the recursion?

Author
Thread Post new topic Reply to topic
CandyMan



Joined: 04 Sep 2009
Posts: 382
Location: film "CandyMan" directed through Bernard Rose OR Candy Shop
CandyMan 08 Dec 2022, 18:20
How to get rid of the recursion in the example below?
I could use a list, but how?
Code:
procedure tOptomizer.DoExpression( var CodeTree: pCodeTree);
  begin
    if Assigned( CodeTree) then
      begin
        DoExpression( CodeTree^.Left);
        DoExpression( CodeTree^.Right);
        case CodeTree^.Node.CodeType of
...    

_________________
smaller is better
Post 08 Dec 2022, 18:20
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3555
Location: vpcmipstrm
bitRAKE 09 Dec 2022, 06:08
ChatGPT says:

One way to get rid of the recursion in the example you provided is to use a stack to store the nodes that need to be processed. Here is an example of how this could be done:
Code:
procedure tOptomizer.DoExpression( var CodeTree: pCodeTree);
var
  stack: array of pCodeTree;
  i: integer;
begin
  // Initialize the stack and push the root node onto it
  SetLength(stack, 1);
  stack[0] := CodeTree;

  // Process nodes from the stack until it is empty
  i := 0;
  while i < Length(stack) do
  begin
    // Pop the top node from the stack
    CodeTree := stack[i];
    Inc(i);

    // Push the left and right children of the node onto the stack
    if Assigned(CodeTree^.Left) then
    begin
      SetLength(stack, Length(stack)+1);
      stack[Length(stack)-1] := CodeTree^.Left;
    end;
    if Assigned(CodeTree^.Right) then
    begin
      SetLength(stack, Length(stack)+1);
      stack[Length(stack)-1] := CodeTree^.Right;
    end;

    // Process the node
    case CodeTree^.Node.CodeType of
      ...
    end;
  end;
end;    
This approach eliminates the need for recursive function calls and can help avoid stack overflow errors that can occur when the recursion is too deep. It works by using a stack to store the nodes that need to be processed, and then iterating over the stack to process each node in a depth-first manner. This has the same effect as the original recursive implementation, but without using recursion.

_________________
¯\(°_o)/¯ unlicense.org
Post 09 Dec 2022, 06:08
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3555
Location: vpcmipstrm
bitRAKE 09 Dec 2022, 06:11
Or, also says:

To get rid of the recursion in the example code, you can replace the recursive call to the DoExpression procedure with a loop that processes the left and right subtrees of the CodeTree node. Here's one way to do that:
Code:
procedure tOptomizer.DoExpression(var CodeTree: pCodeTree);
var
  CurrentNode: pCodeTree;
begin
  CurrentNode := CodeTree;
  while Assigned(CurrentNode) do
  begin
    // Process the left subtree of the current node
    if Assigned(CurrentNode^.Left) then
    begin
      DoExpression(CurrentNode^.Left);
    end;

    // Process the right subtree of the current node
    if Assigned(CurrentNode^.Right) then
    begin
      DoExpression(CurrentNode^.Right);
    end;

    // Perform the appropriate operation based on the current node's code type
    case CurrentNode^.Node.CodeType of
    // ...
    end;

    // Move to the next node in the tree
    CurrentNode := CurrentNode^.Next;
  end;
end;    
In this example, the DoExpression procedure uses a loop to iterate through the nodes of the CodeTree in a depth-first manner. For each node, the left and right subtrees are processed recursively (using the original DoExpression procedure), and then the appropriate operation is performed based on the node's code type. This allows the DoExpression procedure to process the entire CodeTree without the need for recursion.
Post 09 Dec 2022, 06:11
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3555
Location: vpcmipstrm
bitRAKE 09 Dec 2022, 06:15
I pasted your exact text to ChatGPT, and then used the "Try again" option (I like the second response, it's still recursion though, lol).
Post 09 Dec 2022, 06:15
View user's profile Send private message Visit poster's website Reply with quote
CandyMan



Joined: 04 Sep 2009
Posts: 382
Location: film "CandyMan" directed through Bernard Rose OR Candy Shop
CandyMan 09 Dec 2022, 13:31
Thanks a lot! You are a great bitRAKE.
Post 09 Dec 2022, 13:31
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3555
Location: vpcmipstrm
bitRAKE 09 Dec 2022, 19:33
I haven't programmed in Pascal in over 20 years. Although I could provide examples in other languages, it's best to let the AI construction one in Pascal.

From a performance standpoint I like to use recursion because the stack (RSP) is usually in the data cache. Since the entry point is the same there is no need to push return addresses on the stack (don't use CALL) and termination can be handled with a sentinel on the stack. (If null is used for the stack sentinel then left/right will need to be handled internally to insure null is not pushed on the stack.)

_________________
¯\(°_o)/¯ unlicense.org
Post 09 Dec 2022, 19:33
View user's profile Send private message Visit poster's website Reply with quote
CandyMan



Joined: 04 Sep 2009
Posts: 382
Location: film "CandyMan" directed through Bernard Rose OR Candy Shop
CandyMan 09 Dec 2022, 21:56
Small fix. In the first example that you cited the last "case" block, it should be executed in a separate loop and backwards. But thanks.
Post 09 Dec 2022, 21:56
View user's profile Send private message Reply with quote
Furs



Joined: 04 Mar 2016
Posts: 2022
Furs 10 Dec 2022, 18:18
bitRAKE wrote:
From a performance standpoint I like to use recursion because the stack (RSP) is usually in the data cache. Since the entry point is the same there is no need to push return addresses on the stack (don't use CALL) and termination can be handled with a sentinel on the stack. (If null is used for the stack sentinel then left/right will need to be handled internally to insure null is not pushed on the stack.)
Since we program in asm, also keep the parameters in registers if you can, so you don't need to use indirection to access the "context".

But note that this only works if you know the maximum recursion depth. In the original post, it looks like some expression parser, and if that can be arbitrary user input, I think it's dangerous since it can lead to stack overflows.

But for example, a balanced binary tree with recursion is perfectly fine, since you know the maximum height is very reasonable (~log2(items)). Even with 2⁶³ items it will only have depth of 64.
Post 10 Dec 2022, 18:18
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2023, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.