In this paper, we propose a formulation of the permutation flow shop scheduling problem (PFSP) by special recursive functions and show its equivalence to the existing classical formulation. Equivalence is understood in the sense that both ways of defining the problem describe the same set of feasible schedules for each pair of job and machine numbers. In fact, this paper attempts to use the apparatus of recursive functions for scheduling problems. Moreover, the predicate "and" is introduced into the problem, and the problem PFS is expanded from a chain of machines to an acyclic graph. To construct an optimal schedule, the branch and bound method is considered based on the recursive function, which is included into the corresponding job permutation algorithm. The complexity of the optimization algorithm does not increase compared to the non-recursive PFS problem. Finally, we present some initial computational results.