CodeAttack – Recursion Introduction
Usually oneself as a coder has to deal with problems where the informatic solution is obvious or almost obvious. I mean that usually one wanders in already well-known lands, where most of the systems have been studied so much that there doesn’t seem to be very much space for innovation. But not all problems waiting for us out there are as simple as they seem. What really happens is that those who look suspiciously easy to understand are those which are so complex in their solution. Many of those give headaches to the mathematics theorist, but we don’t have their capabilities but we do have the need to solve the same problems, at least we’ll try to do the best we can.
This problems are not that unusual as you may think, for example, suppose in an ecommerce we have shipping system that charges by the amount of boxes sent, and each item has a different volume. We wish to provide the client with the best possible configuration to minimize the shipping cost. It’s not as easy as it seems, isn’t it?
Take note that some of this problems are “bounded”, which means that even if we don’t know the solution, we know is between a finite amount of possibilities. Then, we could just check every possible configuration till we found one that solves the problem. This solution is known as “brute force”, and it’s not the most efficient, but it is a solution we can work out with our capabilities, and, most of the times, we don’t need that much efficiency.
Anyway, although we know a solution, sometimes is not that simple to put it into practice, and most of the times the result is not as nice as we would like. But, there is a technique that we can use to provide an elegant solution to this kind of problems: recursion.
Basically, with recursion we solve one step of the problem knowing that we can solve the problem with a smaller input, for example, we have a bag of coins with different values, and we want to obtain an exact sum of money using those coins. We will solve a problem having N coins, assuming that the solution for a bag of N-1 coins is known.
Therefore, if we take one coin from the bag, we known that the problem for the remaining coins can be solved. We have to use that to solve the problem considering the coin we took. We could check if there is an ammount of money requested in the bag without the coin, and if there is, we have a solution. If not, we have to consider the possibility that the coin we took was needed. We assume that coin was part of the solution, and recheck the bag for the ammount requested minus the value of the coin taken. If there is a solution, we just put the coin in it and we have a solution por the original ammount. If these cases fails, we can say that there isn’t a solution.
In pseudo-code:
function obtainAmmount(bag, ammount) when the bag has N coings
coin <- bag.takeCoin()
solution1 <- obtainAmmount(bag, ammount)
if solution1 exists
return solution1
else
solution2 <- obtainAmmount(bag, ammount - coin)
if solution2 existe
solution2.putCoin(coin)
return solution2
else
return there is no solution
Now the solution for N coins uses the solution for N-1 coins, and this one uses the solution for N-2 coins, and so on. For the recursion to work, we have to find a solution that doesn’t depend on another. This one is called the “base case”, and it’s generally an instance of the problem that is trivial to solve. In the example the basic case would be the problem with an empty bag, for this problem there can be only one solution: an empty set when the ammount requested is zero.
In pseudo-code:
function obtainAmmount(bag, ammount) when there are no coins in the bag
if ammount = 0
return empty solution
else
return there is no solution
Finally we can combine these to get one complete solution:
function obtainAmmount(bag, ammount)
if the bags has no coins
apply base case
else
apply recursive case
That’s it. Observe that, for each coin, we check the possibility that it’s used in the solution or not, therefore, we’re actually going through each possible combination sequentially till we found one that fits the requirements. This happens in most recursions, so it’s a good guideline to know how many recursive calls are needed in the recursion case.
