In this work, I propose a new method for the computation of informational entropy from Recurrence Plots when the analyzed time series are categorical in nature. In such cases, there is typically a simplification in choosing the parameters of the analysis, in the sense that no embedding in multidimensional space is usually assumed and that recurrence is restricted to exact matching (equivalence) of the numerically coded categories. However, such a simplified parameterization brings about some notable changes in the appearance of the obtained Recurrence Plots, which has consequences for the extraction of the standard dynamical measures. Specifically, a categorical Recurrence Plot is often composed of rectangular structures rather than line structures (diagonal and horizontal/vertical), over which the recurrence quantification measures were originally proposed. Starting from this observation, I consider alternative computational procedures to extract a non-biased measure of entropy for the categorical case, showing the viability of such a choice with simulated data