Lab #5, Wednesday 9/27

The purpose of this lab is to give you some practice with recursion.

Pidgey Calculator

In Pokemon Go, a common Pokemon is the pidgey. In the game you can catch many pidgeys. Since the game's release, an avid Pokemon Go player has probably caught thousands of pidgeys! Some players use pidgeys as a way to gain experience points and level up.

As you collect pidgeys you also collect pidgey candy. If you have at least 12 pidgey candies then you can use them, along with 1 pidgey, to evolve the pidgey into a pidgeotto. This earns you experience points. (The evolution also requires stardust and enough pidgeys, but ignore that for this problem). Performing the evolution consumes the 12 candies, but gives you back one candy for the new pidgeotto. If you transfer the pidgeotto, this gives you an additional candy (transferring is like exchanging the pidgeotto for a candy). Assuming you always transfer an evolved pidgeotto, this means that each pidgey evolution requires 12 candies but gives you back 2 candies from the evolution and transfer.

We are interested in computing the maximum number of pidgeys we could evolve given a certain number of candies.

For example, if you had 140 candies:

You have evolved a total of 13 pidgeys.

Write a program with a recursive function that takes as input the number of pidgey candy that you have. The function should return how many pidgey you could evolve, using the rules and procedure stated above. Your program should not use any global variables.

Test your function with these numbers to see if it is working:

  With 80 candies, you could evolve 7 pidgeys.
  With 140 candies, you could evolve 13 pidgeys.
  With 230 candies, you could evolve 22 pidgeys.
  With 300 candies, you could evolve 29 pidgeys.
  With 6613 candies, you could evolve 661 pidgeys.

Complete or email to by midnight for lab credit.