Partially regular recurrent lattices, are k-space grids that we propose, which consist of a central regular region that is extended using a recurrence relation, resulting in an asymptotically logarithmic lattice structure. Such a lattice can be used to model the turbulent cascade over a very large range of scales covered by the recurrent part, while keeping the large scale eddies mainly in the regular part. Here we propose a novel pseudo-spectral algorithm for computing the convolutions over such a lattice, using an overlapping partition of its different parts, using the fact that the interactions in the recurrent part of the lattice are limited, in each direction, to a small number of elements linked through the recurrence relation. We compare the results with a full grid, dense, fast Fourier transform (fft) based convolution, where the nonexistent elements on the full grid are set to zero, and show that the difference remains within a few orders of the machine precision. The algorithm in two dimensions uses one fft for the regular grid, and bunch of smaller ffts for the rest of the points, either elongated to match the length of the regular part of the grid in one dimension or even smaller ffts (typically) to include the interactions between recurrent parts of the lattice. The algorithm can be trivially generalized to arbitrary number of dimensions.