324: Mainline

For another, more interesting illustration of recursion, suppose that you have discovered a miraculous diet that always leads to weight loss without any negative side effects. Your publisher tells you to write a book, and assures you that the sales will multiply “like rabbits” each month for at least 2 years. You wonder if that remark is fantastic news, or just a silly metaphor.

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.