Using recursion to get rich!
In this first example, we show how a fundraiser might use the principles
of recursion to collect a large sum of money for some worthy cause.
Suppose that you were the fundraiser and that you wished to collect
£1000 pounds for some worthy cause by selling lottery tickets at
£1 each. There are many ways in which you might approach the
task. You might go from door to door selling these tickets
until you had visited 1000 houses willing to buy a ticket. This approach
could be very time consuming on your behalf and would require a high degree
of motivation.
You might however decide to use a more recursive technique, instead
of selling all the tickets yourself you instead seek out ten like
minded people and ask each of those ten to collect £100 each
thus simplify the problem for each of the sub collectors. Now each
of those collector your recruited might also use the same technique and
solicit the aid of 10 further collector to collect £10 each.
Those collector now need only find ten people willing to contribute £1
for the ticket.
The recursive aspect of this technique is the way in which each sub
collector is asked to perform the same task (i.e. sell tickets), however
the amount the the sub collectors must collect is reduced in difficulty
(i.e. simplified £1000, £100, £10 ) until eventually
a base condition (i.e. the base case) is reached where
the collector need only contribute £1 directly themselves.
This strategy for solving problems is often referred to as "divide
and conquer". The problem is divided up in to simpler and
simpler instances until a point is reached where the problem can be overcome
directly.
The Money Collector applet which accompanies this page shows how this
method of collection might be coded in Java.
|
-
In section A of the animation window the Java source code
of the algorithm can be viewed. The flow of execution can be followed line
by line as the algorithm executes.
-
In area B of the window an animation illustrating the workings
of the algorithm can be seen. In this applet it is interesting to
watch the way the money collection process works. The top collector first
recruits one sub collector who in turn recruits one collector until eventually
£1 is all that the collector must collect, when enough money has
been collected by the lowest collector he returns his money to his superior
who must at that point recruit a second collector. This may not have been
the way you visualized this algorithm working in your mind.
-
Area C is an advanced feature that you may not initially
want to worry about. This bar graph shows the current level of recursion
along with (up to) 30 previous levels of recursion. If you watch this window
you can notice several aspects of this algorithm, e.g. the levels of recursion
is always equal to the layers to recruit. Can you explain why this might
be? You may also notice that there is a symmetry along the y-axis of the
graph which is related to the number of sub collectors that may be recruited.
-
Area D is a text area which gives a text explanation of the
actions of each line in the algorithm and its purpose and consequence.
This text should explain each line as it executes. If this is changing
too quickly for you to read it use the Speed of Execution control (see
h) to slow down the applet animation.
-
The number of sub collectors to recruit controls how may
sub collectors the task may be spread over. Together with the layers to
recruit this dictates the total amount that can be collected.
-
The number of layers which can this task can be passed down
through. This means how may layers of sub collectors are we willing to
allow this problem to pass through before the base case of £1 should
be collected.
-
The total amount to be collect. You can not directly adjust
this value but by altering the values of the number of layers and the number
of recruits you can decide the amount that will be collected
-
The speed control bar allows you to speed up or slow down
the rate at which the algorithm is executed.
|
