Using recursion

Recursion is a key technique in FP, to the degree that there are some languages that do not provide for any kind of iteration or loops and work exclusively with recursion (Haskell, which we already mentioned, is a prime example of that). A basic fact of computer science is that whatever you can do with recursion, you can also do with iteration (loops), and vice versa. The key concept is that there are many algorithms whose definition is far easier if you work recursively. On the other hand, recursion is not always taught, or many programmers, even knowing about it, prefer not to use it. So, in this section we shall see several examples of recursive thinking, so you can adapt it for your functional coding.

Note

A typical, oft-quoted, and very old, computer joke! Dictionary definition:recursion: (n) see recursion

But, what is recursion? There are many ways to define what recursion is, but the simplest one I've seen runs along the lines of a function calls itself, again and again...