349: Mainline

Now, for another, more interesting illustration of recursion, suppose that your railroad hauls rabbits. You are asked to predict the number of cars that you will need to get the rabbits to market when they are shipped a few months from now.

Fortunately, Fibonacci figured out long ago how fast rabbits multiply, deriving a formula that gives the number of female rabbits after n months, under the following assumptions:

• Female rabbits mature 1 month after birth.
• Once they mature, female rabbits have one female child each month.
• At the beginning of the first month, there is one immature female rabbit.
• Rabbits live forever.
• There are always enough males on hand to mate with all the mature females.