Are all foldable data structures also recursive?

I was checking what Wikipedia has to say on reduce. It says:

In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value.

This raises the question: Are foldable data structures always recursive (or can be seen as such)? This is obvious for things such as lists and trees (in Haskell):

data List a = Nil | Cons a (List a)

data Tree a = Empty | Node (a, Forest a)

data Forest a = Nil | Cons (Tree a) (Forest a)

In other words, are all iterable data structures also recursive?* How would one go about proving this?

*I'm assuming that being iterable is sufficient to be foldable.

• The first step of proving (or disproving) this would be to define your terms. What's a "foldable data structure"? What's an "iterable data structure"? What's a "recursive data structure"? A few examples and/or some suggestive naming don't constitute a definition. – Derek Elkins Jun 23 at 21:07
• As one example of this issue. You can define a fold function for data Bool = True | False which is not a recursive type in the sense that Bool doesn't occur recursively in its definition. It is an inductive type though. Does this count as a recursive data structure? – Derek Elkins Jun 23 at 21:09