(Almost) Automatic Programming: Recursion is a lot easier than you think

Walid Saba, PhD
Aug 19, 2018 · 7 min read

Recursion and recursive programs are often looked at as the ‘unnatural’ way of solving problems, in contrast to iterative programming. But nothing is further from the truth. In fact, it is iterative programs that are the unnatural method of solving problems. Let us take a simple example: suppose we were asked to write a program (a function), called Length, that expects some list (or sequence of objects) as input and is to return an integer, indicating the number of objects in the list. This function can be visualized as shown below:

Usually programmers are ‘programmed’ to write this function iteratively by doing a for-loop (or a ‘while’ loop), by setting an initial counter to 0 and adding 1 in every step of the loop, as follows:

However, I claim this is not the most ‘natural’ way to solve this problem (nor other problems, as we shall see). Instead, let me suggest how the most natural solution can be reached at (almost) automatically. In doing so I will use the syntax of what are known as pure functional programming languages, such as Haskell. All we need to know for now is the notation for a list/sequence, which has the following syntax:

List ::= []
List :: = obj : List

What the above says is this: a list can be either empty (i.e., []), or it has at least one object, obj, followed by (or attached to) another list, which could in turn be empty. As such, any list can be matched with the above pattern. For an example, here’s how a list such as [3, 10, 2, 21] is constructed (or, invesrley, how it can be broken down):

[3, 10, 2, 21]
= 3 : [10, 2, 21]
= 3 : 10 : [2, 21]
= 3: 10 : 2 : [21]
= 3: 10 : 2 : 21 : []

That is, the list [3, 10, 2, 21] is 3 attached to the list [10, 2, 21], and the latter list is 10 attached to [2, 21], which is 2 attached to the list [21], which is 21 attached to [] (the empty list)! Now let us see what is the most natural way of writing the Length function, and how we can even (almost) automatically discover the solution. Let us first write the skeleton of this function. The Length function expects a list as input, and so all we need to do is capture the two input possibilities, which are two: the list can be empty, or it can have at least one object followed by some list (which could in turn be empty). So here is the skeleton function:

What the above says is that the function Length returns ?x if the input list is empty. On the other hand, if the list has at least one element e attached to some other list (that we called rest), we are going to trust that our function will in the end work, and use it to compute the Length of the rest of the list. Now, what should the value of ?x be? That is, what should we return if the input list is [] (empty). Clearly, a reasonable return value for the length of the list in this case is 0. Now what about the second case? Supposing we trust our function will work (that is, if we use it on the rest of the list it will return the length of the rest of the input list), then what should the final result be? Clearly, the final result should be 1 added to (Length rest). So let us fill in what we left out from the above definition:

That is, the Length of an empty list is 0, otherwise, if the list has at least one element e followed by some other list, rest, then the final value is the length of the rest plus 1. That’s it!

Now let us try another function. Suppose we are now asked to write a function that also takes a sequence of numbers but we are now asked to return the Sum of all the numbers in the list. Again, since our input is a list, we have only two possibilities that we need to handle, and, we are again going to to trust that the function we are defining will in the end work and we are thus going to use it while defining it (thus, ‘recursion’)! Here’s the general template that can be written automatically:

There are only two questions now that we need to answer to complete the solution: (i) what is a reasonable value to return as the sum of positive integers if the input sequence is empty; and (ii) what should the final result be if Sum works and the rest of the list, returning the sum of the rest of the list? The answer to the first question is clearly 0, and the answer to the second question is that all that is left to do is add the first element, e, to the sum of the rest to return the sum of the entire list. Thus,

Now some might not yet be convinced, but this really is a powerful way to almost discover the solution to complicated problems almost automatically. To convince you (or get you close to that), here are incomplete templates that can be written automatically to solve a number of problems:

Let us start finishing the above templates (that, again, can be written immediately and automatically!) First, let us finish the function member. If we are testing whether some n is a member of some list, what should we return if the input sequence is empty? Clearly, the result in this case should be False, since n could not be a member of an empty sequence. Now what about the general case? Again, assuming we trust our function will work and we can use it on the rest of the list, then n is a member of the entire list if it is equal to the first element e, or if it is a member in the rest of the list. Thus:

Done!

Now let us complete the definition of the function count_occurance. Again, what should we return if the input sequence is empty? That is, how many times would n occur in an empty sequence? Clearly, the result in this case should be 0. And what if we again trust that our function will ultimately work and we can use it on the rest of the list. That is, what if (count_occurance n rest) does in fact return the number of times n occurs in the rest of the list, then what is the final result — the number of times n occurs in the entire list? Clearly, if n equals the first element also, then it is 1 plus the the number of times n occurs in the rest of the list, otherwise it is just the number of times n occurs in the rest of the list. Thus,

Using the same strategy, we can define reverse. Now the reverse of an empty list is an empty list, and the reverse of a list (e:rest), if we trust that our function will work and thus reverse works on the rest, is simply a list that has only e in it appended to the reverse of the rest. That is,

And here’s how that will actually work (execute), where ‘++’ is the append function between two lists:

We leave the dec_value function as an exercise. But here’s how one can sort in two lines:

That is, the sort of an empty list, is an empty list; otherwise, the result is simply inserting the first element e in the right place in the rest of the list sorted. Of course, that means we now need to define the function insert which takes a number n and a sorted list seq, and returns a list where n is inserted in the right place in the sorted list seq. Here’s the template of that function that we can, also, automatically write:

We leave to you to finish the above template.

Recurse, and discover solutions (almost) automatically!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade