@valleyforge do you mean recursion based on the two examples you provided (factorial and Fibonacci)? Functional programming is not just limited to recursive functions and is a declarative programming paradigm:
https://en.m.wikipedia.org/wiki/Functional_programming
@valleyforge Mergesort is also an excellent example of recursion.
@sojournTime recursion is a great example of functional programming and those are great examples of recursion so they tend to get used in intros to functional programming