The Money Collector.

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

The Money Collector applet which accompanies this page shows how this
method of collection might be coded in Java.

  1. 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.
  2. 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.
  3. 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.
  4. 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
    ) to slow down the applet animation.
  5. 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.
  6. 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.
  7. 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
  8. The speed control bar allows you to speed up or slow down
    the rate at which the algorithm is executed.