This study presents recursive relations on the permanents of k − tridiaonal Toeplitz matrices which are obtained by the reduction of the matrices to the other matrices whose permanents are easily calculated. These recursive relations are achieved by writing the permanents with bandwidth k in terms of the permanents with a bandwith smaller than k. Based on these recursive relations, an algorithm is given to calculate the permanents of k − tridiaonal Toeplitz matrices. Furthermore, explicit combinational formulas, which are obtained using these recurrences, for the permanents are also presented