The thing that students have the hardest time on when learning functional programming is how to process a recursive structure while maintaining some sort of "state", the result if you will. I'll attempt here to demystify the process.

Functional programming languages almost always use a lot of recursively defined structures. Depending on the language those can be implemented in various ways, but in any case the end result is the same. A structure of this type is either an "atom", i.e. an irreducible thing, or a "compound" consisting of substructures of the same form.

For example a "list" is either an Empty/Nil list (the "atom") or it is formed as a Cons of a value and another list (compound form). That other "sublist" can itself be empty or another cons and so on and so forth. A tree is similar. It is either empty, or it consists of a triple of a value and two sub-trees, left and right.

Almost every problem we encounter is a question about doing something with all entries in a structure. To solve these prob