The Church encoding allows definition of certain recursive functions, but all the recursive calls are implicit.  The encoding simply presents you with the results of recursion for all immediate subdata.  Using a technique due to Mendler, an encoding is possible where recursions are explicitly made by the combining functions given to the data.