Loops and Recursion

Sometimes when you look at breaking down a complex problem into several simpler ones you find that those simpler problems might be the same or similar to each other. For example when we considered the joke about the logicians being asked if they all wanted a drink the "processing" each needed to do in order to provide an answer is similar to what each of the others needs to do. When we can break a problem into a series of smaller problems that are similar to each other then we can implement the solutions to these smaller problems by using a loop or by using recursion. Which of these that you would use would depend on how you intend to implement each of the smaller solutions.

Any problem that could be solved using a loop could also be solved using recursion and vice versa and so one of the decisions that you need to make once you decide that the problem can be solved by repetitive executions of the code to solve a simpler problem you then need to decide which of the two approaches to take. In fact as there are several ways that both looping and recursion can be implemented you actually have more alternatives to choose between than just whether to use a loop or to use recursion.

In the case of recursion you can either have the recursive call occur first followed by the rest of the code or have the rest of the code occur first followed by the recursion. In some rare cases you may have two recursive calls with the code in between.

With loops you can either loop forward or loop backward. In some instances you will have situations where the loop might be able to be terminated early where certain conditions are met.

When trying to solve a problem that looks like it is able to be broken up into a series of similar problems it is worth considering all of these different ways of implementing the repetition until you find the one that will make solving the repetitive problems easiest. Finding the simplest solution at least proves that the problem is solvable by breaking it up into this series of smaller repetitive problems. This doesn't mean that we are going to actually use that solution though as solutions that use loops or recursion are far less efficient solutions than ones that don't. We saw this in the early example where we wanted the sum of a series of consecutive integers.

Where we have found a solution that involves a loop it is always worth spending some time to see if we can find a way to eliminate the loop or if completely eliminating the loop is not possible then a way of rearranging the loop so as to minimise the number of executions of the code within the loop that will be needed.

Any code using recursion can be rewritten to use a loop. The loop in these cases will generally be somewhat more complex than those where we didn't need to consider recursion to solve the problem but usually the loop version can be arranged so that it runs more efficiently than the recursive version even though it may not be as easy to understand. Also with recursion, code that does the recursion last will often run more efficiently than code that runs the recursion first - often the compiler will be able to treat such code as if it were written using a loop allowing you to write easier to follow code while keeping the code easier to read.

Finding a solution that uses a loop or recursion and then refining it to make it more efficient is one way of getting to a solution that you may not have been able to get to directly. Sometimes while refining the efficiency of the code you will identify patterns in what the code is doing that will make it obvious that a solution that doesn't require a loop is a possibility. Even where a loop or recursion ends up being required as a part of your solution, examining the various alternative ways of coding this will help you to improve your understanding of the overall problem and so may provide you with additional ideas as to other alternative ways to solve the problem.

After you have found a solution to the overall problem you need to consider whether a better solution might exist. This applies particularly where the solution that you have found involves a loop or recursion.

 

This article written by Stephen Chapman, Felgall Pty Ltd.

go to top

FaceBook Follow
Twitter Follow
Donate