flat assembler
Message board for the users of flat assembler.

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

Joined: 04 Sep 2009
Posts: 384
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
08 Dec 2022, 18:20
bitRAKE

Joined: 21 Jul 2003
Posts: 3624
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.

_________________
09 Dec 2022, 06:08
bitRAKE

Joined: 21 Jul 2003
Posts: 3624
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.
09 Dec 2022, 06:11
bitRAKE

Joined: 21 Jul 2003
Posts: 3624
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).
09 Dec 2022, 06:15
CandyMan

Joined: 04 Sep 2009
Posts: 384
Location: film "CandyMan" directed through Bernard Rose OR Candy Shop
CandyMan 09 Dec 2022, 13:31
Thanks a lot! You are a great bitRAKE.
09 Dec 2022, 13:31
bitRAKE

Joined: 21 Jul 2003
Posts: 3624
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.)

_________________
09 Dec 2022, 19:33
CandyMan

Joined: 04 Sep 2009
Posts: 384
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.
09 Dec 2022, 21:56
Furs

Joined: 04 Mar 2016
Posts: 2103
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.
10 Dec 2022, 18:18
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum