You still hit the same issue and you can still solve it the same way by converting that class with saved state into just a function.

Below are two short examples of two different ways to do this:

   type Node = Null | {value: int, left: Node, right: Node} 
   //a Node is NULL or a value that is an int with left and right nodes

   //procedural with mutation, saved state is placed in parameter: found
   def find_n_and_print_all_DFS (node: Node, search_value: int, &found: Node) -> Void:
      if node == Null:
         return
      else:
         print(node.value)
         *found = node.value == search_value ? node : Null
         find_n_and_print_all_DFS(node.left)
         find_n_and_print_all_DFS(node.right)


   //functional, no mutation, saved state is returned
   def find_n_and_print_all_DFS (node: Node, search_value: int, found: Node = Null) -> Node:
      if node == Null:
         return found
      else:
         print(node.value)
         found = node.value == search_value ? node : Null
         left = find_n_and_print_all_DFS(node.left, found)
         right = find_n_and_print_all_DFS(node.right, found)
         return left != Null ? left : right

I would argue that if I used classes the code would be way harder to read and much more verbose.

You can essentially use tail recursion on that DFS and pass in some accumulator as a parameter into your DFS or whatever. That accumulator can be some pointer representing some saved state or anything you want. There is still no need to group everything together into an Object.

It's a bit trickier but in the second example you can see that you don't even need to mutate anything at all. What you described can be achieved without redundant OOP classes and without mutating state at all! Additionally setting found to have a default value of Null negates the need for the extra accumulator parameter during function calls as you can just call it like this:

     saved_node = find_n_and_print_all_DFS(x, 5)

I would still say OOP is an anti pattern because it overall promotes adding these mutating parameters in your code even when you don't need save states or anything of that nature. In OOP, the existence of getters and setters and methods for accessing variables outside of the definition of the method itself heavily promotes this type of coding style regardless of whether or not it is needed.

The procedural style forces this additional "saved" feature to be evident as an extra parameter. If you never use that parameter it becomes obvious that the parameter is redundant while in OOP mutating external state is an intrinsic part of the style and like the OPs example you have to go through several logical leaps to see how redundant it is.