In this paper, we will present various results on computing of wide classes of Hessenberg matrices whose entries are the terms of any sequence. We present many new results on the subject as well as our results will cover and generalize earlier many results by using generating function method. Moreover, we will present a new approach on computing Hessenberg determinants, whose entries are general higher order linear recursions with arbitrary constant coefficients, based on finding an adjacency-factor matrix. We will give some interesting showcases to show how to use our new method.