flat assembler
Message board for the users of flat assembler.
![]() |
Author |
|
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; |
|||
![]() |
|
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; |
|||
![]() |
|
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).
|
|||
![]() |
|
CandyMan 09 Dec 2022, 13:31
Thanks a lot! You are a great bitRAKE.
|
|||
![]() |
|
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.) |
|||
![]() |
|
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.
|
|||
![]() |
|
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.) 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. |
|||
![]() |
|
< Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2025, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.