Recent work on recurrence in quantum walks has provided a representation of Schur functions in terms of unitary operators. We propose a generalization of Schur functions by extending this operator representation to arbitrary operators on Banach spaces. Such generalized Schur functions meet the formal structure of first return generating functions, thus we call them FR-functions. We derive general properties of FR-functions, among them a generalization of the renewal equation already known for random and quantum walks, as well as splitting properties which extend useful factorizations of Schur functions. When specialized to self-adjoint operators, FR-functions become Nevanlinna functions. This leads to new results on Nevanlinna functions: decomposition rules which are the analogue of useful factorizations of Schur functions, a simple Nevanlinna version of the Schur algorithm and new operator and integral representations of Nevanlinna functions which, in contrast to standard ones, are exact analogues of those already known for Schur functions, giving similarly a one-to-one correspondence between Nevanlinna functions and measures on the real line. The paper is completed with several applications of FR-functions to orthogonal polynomials and random and quantum walks which illustrate their wide interest: an analogue for orthogonal polynomials on the real line of the Khrushchev formula for orthogonal polynomials on the unit circle, and the use of FR-functions to study recurrence in random walks, quantum walks and open quantum walks. These applications provide numerous explicit examples of FR-functions and their splittings and show that these new tools, despite being extensions of very classical ones, play an important role in the study of physical problems of a highly topical nature.