Recreate a fragment from scratch or use the backstack?

I have to develop a questionnaire app that shows a sequence of 8 different screen layouts, each screen with different data. The particular sequence depends on the user's previous responses. So it might go something like this:

A > B > B > B > C > B > B > D > D > D > D > D > D > D > D > D > E > F > F > F > F > B > B > G > F > F> etc

The sequence of questions might be as long as 500 questions (according to the requirements). When the back button is pressed, some of these screens should be skipped (for example you might not show some of the F or some of the D).

I'm new to android and perhaps didn't make the best choices: I have 1 activity for the questionnaire and multiple fragments (A, B, C, D, etc) that are presented consecutively according to the questionnaire's logic and the user's previous replies. Going back is done with the use of the backstack. There have been a lot of problems with going back and then again forward (keeping the correct state/ keeping the correct data in the fragment / memory issues etc).

At this point the app has gotten so convoluted and buggy that I'm considering perhaps scrapping the backstack. Maybe I could just put the sequence of fragments in the database as I go forward (meaning just the type of fragment and a few associated ids), then retrieve the relevant data from the db and recreate the previous fragment from scratch in the onBackPressed method if the back button is pressed. It seems cleaner and perhaps less prone to unexpected behaviors (?) especially since i'm inexperienced in android.

Is this an acceptable solution? How would creating the fragment each time affect memory performance and cpu performance? What would be the disadvantages or advantages of this approach? What in your opinion would be the best architecture for this particular app?