Writing Recursive Functions

Solving problems with recursion

Coming from an imperative programming language to Haskell, getting used to writing recursive functions can be challenging. Programs with loops are inherently imperative (e.g. for each of these values, do these things) and often make use of mutable variables. Writing programs this way shapes our way of thinking about problems and coming up with solutions to them.

To create recursive solutions will require a radically different way of thinking about the problem. While this may seem daunting at first, it often leads to us understanding the problem at a deeper level and discovering new properties about it. Not only are the recursive solutions free of side effects and mutable states, often they are shorter and more elegant than their imperative counterparts.

In general, there are two main steps in finding recursive solutions:

1. Identify easy cases for the problem. These will be the base cases of the recursion.
2. Find a way to solve more complex cases by adapting or combining solutions for smaller cases. These will be the recursive cases of the recursion.

Often, recursive Haskell functions will end up with two equations: one for the base case, as well as one for the recursive case. In this lesson, we will study some more examples of different flavors of recursive functions.