An interplay between the Lambert series and Euler's Pentagonal Number Theorem gives an Euler-type recurrence relation for any given arithmetical function. As consequences of this, we present Euler-type recurrence relations for some well-known arithmetic functions. Furthermore, we derive Euler-type recurrence relations for certain partition functions and sum-of-divisors functions using infinite product identities of Jacobi and Gauss.