I know that Fragment should be created and added to the manager using FragmentTransaction when the fragment is used for the first time. But later it can be found by findFragmentById or findFragmentbyTag after configuration changes such as screen rotation.
But on screen rotation, I found that the constructor and all the call back methods of the fragment onAttach, onCreate, onCreateView, onStart, onResume are called again, even if the fragment is returned from findFragmentByTag not explicitely calling the constructor.
The fact that the constructor is called implies that the fragment object can be garbage-collected. Then what part of the fragment is actually stored on configuration changes? If the fragment object is garbage-collected and recreated, then what is the purpose of recyling it?
The fragment is not recycled. If you logged Fragment.toString() after screen orientation, you would get a different value meaning those fragment instances are different, created from scratch. All lifecycle methods are called BUT you are able to persist some values through onSaveInstanceState(Bundle).
This is not true for fragments where you called setRetainInstance(true). Now the only lifecycle methods that are repeating are onCreateView, onViewCreated, (long pause), onDestroyView. The instance is the same, the field variables are retained.
EDIT:
Does Android OS automatically destroy and create the fragment and set the same Tag and ID before onCreate is called on the hosting Activity?
TL;DR: Yes.
The FragmentState class field variables contain information about one fragment which is always retained (among others tag and id).
When you rotate screen FragmentManagerImpl.restoreAllState(...) is called which either grabs retained fragments or instantiates new fragments and reattaches them to the new activity. This happens as part of Activity.onCreate(Bundle).
Then what part of the fragment is actually stored on configuration changes?
The FragmentState as described above plus anything you or the framework writes in onSaveInstanceState(Bundle). If the fragment is marked as retained, everything except view hierarchy is saved.
If the fragment object is garbage-collected and recreated, then what is the purpose of recyling it?
If it's destroyed and created from scratch (new instance) it's not recycling at all. You either retain the fragment instance - the same instance survives screen orientation change - or save and restore instance state - old fragment instance is destroyed, new fragment instance is created and filled with some data from the old instance.