Iteration and recursion are two ways to repeat a set of instructions. Iteration involves using loops to control the repetition. Loops can be either counter-controlled or sentinel-controlled. Counter-controlled loops repeat a set of statements a prescribed number of times, while sentinel-controlled loops keep repeating until a certain condition no longer holds to be true. Recursion, on the other hand, generally doesn’t use loops, although loops can certainly be used to implement some of the logic of a recursive routine. Instead, a recursive function implements repetition by repeatedly breaking down a given problem into smaller, simpler versions of the original one, until that repeated decomposition yields a problem that is so simple that no work can be done to simplify it further. That final version of the problem – the base case – represents the stopping point.
Let’s consider an example of each. The program below uses two kinds of iteration: counter-controlled and sentinel-controlled. A counter-controlled loop is used to fill the cabinet. A sentinel-controlled loop is used to divide usa in half until it declines to nothing.
Basically, as long as America isn’t great again, keep having the various agents, which are all members of cabinet that were created with various traits and levels of wealth, do their part in making America great again. The function that makes America great again does so by dividing usa in half. The agents keep dividing usa in half until it has become great again, which, in this simulation, is the point at which it has been reduced to nothing. It’s at that point that the is_great_again question will return True, indicating that, at long last, America has finally become great again, at least given the assumptions of this simulation.
That is the iterative approach. We can achieve the same aims using recursion. Remember that recursion involves repeatedly breaking a problem down into its component pieces until we have broken the problem down so much that it cannot be reduced further. Here is the recursive approach, with the recursive function – the one that does the repeated decomposing of the problem until we arrive at that simplest version – outlined in a rectangle.
The recursive function in this example is called make_america_great_again. It takes in usa as the thing it operates on. It proceeds by subdividing usa in two until it is reduced to nothing, at which point the function will return the value True. The base case here is the situation where usa has become nothing. That is the point at which the program’s work is complete.
The problem with this approach is that, like most recursive solutions, it ends up using a lot more resources in the process. However, it is, arguably, the more elegant way to achieve the intended outcome. In other words, it accomplishes its work with a certain air of sophistication and style at the risk of being a bit wasteful in the process. The other interesting thing about this version is that the cabinet here was really just for show. Notice that the cabinet members didn’t directly work to divide usa. Instead, the system diminishes usa to nothing, without anyone taking ownership of the task.
So, there you have it: two different ways to simulate the reduction of a value through repetition. Regardless of the approach we took – iterative or recursive – and whether the cabinet or the system itself performed the meaningful deeds, we ended up with nothing in the end, which is exactly what we wanted.
And now you know how it works.