Should I format my disk when reinstalling macOS? I'm having some issues with my 16 inch MacBook Pro. It restarts and gives me the "Your computer was restarted because of a problem." prompt. It has done that 5 or 6 times so far. I was advised to do a recovery.

Apparently, you can reinstall macOS without wiping the disk. You can also reinstall and wipe as well. And if you go even further, you can reinstall and start from scratch without any data or apps. 

Is it preferable to go all the way and start from the beginning, like how it was on the day it shipped?
Yes - it’s the perfect time and often sets you up for the best experience.
Your question is hard to answer absolutely since it does take a bit more time and some people don’t have confidence or skill in their backups. You can’t get the image Apple provides since it has non-registered versions of the free apps to claim. But on all the supported OS (N-2 with N being Catalina on October 1, 2020) are free and you can download them easily after an erase. I especially recommend an erase install if you want to be sure the hardware isn’t the cause of issues. You don’t have a better test than this in my experience.
Installing on top of a corrupt partition / volume / system won’t fix that, but will restore the OS cleanly. Make a backup and check your important files are intact on the backup and erase-install is my go to move.
You get to test a clean slate and then do the erase a second time if needed then restore files back. It takes a little extra time, but you never have to redo a step and build confidence the hardware is good sooner than an overlay install.