Are all foldable data structures also recursive?
No, not all foldable data structures are recursive, although the in the non-recursive case what we have is really a degenerate version of a fold.

For example, we can view the function if : Bool -&gt; a -&gt; a -&gt; a as a fold over the type Bool.

In general, when dealing with recursive or non-recursive types, the fold are called eliminators, since they are how we consume values of a given datatype. Eliminators are particularly interesting for dependent types and indexed type families, where the eliminator corresponds to an induction principle for that data type. See this paper for more info on this.

Eliminators always terminate, which means that if you have only eliminators (in place of general recursion) you will not be Turing Complete. You can even encode a data structure as its eliminator, using something called Church Encodings. Using this, you can write lists and other data types in a language that only has functions, like System F.