  We study numerically the statistics of Poincar\'e recurrences for the
Chirikov standard map and the separatrix map at parameters with a critical
golden invariant curve. The properties of recurrences are analyzed with the
help of a generalized Ulam method. This method allows to construct the
corresponding Ulam matrix whose spectrum and eigenstates are analyzed by the
powerful Arnoldi method. We also develop a new survival Monte Carlo method
which allows us to study recurrences on times changing by ten orders of
magnitude. We show that the recurrences at long times are determined by
trajectory sticking in a vicinity of the critical golden curve and secondary
resonance structures. The values of Poincar\'e exponents of recurrences are
determined for the two maps studied. We also discuss the localization
properties of eigenstates of the Ulam matrix and their relation with the
Poincar\'e recurrences.
