How to write complex recursive code cleanly?

I am writing a module in Java that works recursively and has very complex logic. Because the recursive nature of the problem I am trying to solve not using recursion is not an option.

What makes the logic of my program complex include: 1-properly detecting and handling different special cases 2- correctly set or unset some flags which are going to be used when the code returns from the recursion. 3- having a logic that works mostly lazily but for some part it has to work eagerly.

My code has become around 1500 lines of complex and highly coupled code which has made finding errors and bugs a nightmare which sadly they are not rare. I have already have tried separating the logic in smaller pieces and take advantage of OO paradigm and encapsulating each part of logic but the code still hard to understand. I was wondering if there are any design patterns, guidelines or conventions for writing clean and understandable complex recursive code? I have looked around online but I did not found anything really useful.