Lab #5, Friday 2/16

The purpose of this lab is to give you more 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 a pidgey, but ignore that for this problem). Performing the evolution consumes the 12 candies, but gives you back one candy for the new pidgeotto. You have the option to "transfer" the pidgeotto to professor Willow. In exchange, you get a single pidgey candy. Assuming you always transfer an evolved pidgeotto, this means that each pidgey evolution requires 12 candies but gives you back 2 candies, one from the evolution and another from the transfer.

We are interested in computing the maximum number of pidgeys we could evolve given a certain number of candies. There is no simple mathematical formula where you can plug in the number of candy you have and calculate the number of pidgeys you can evolve, because transferring enough pidgeotto eventually results in enough candy to evolve more pidgeys. However, we can solve this problem with a recursive program.

Here is an example solution if you had 140 candies:

• You could use 132 of those candies to evolve 11 pidgeys (11*12=132) leaving you with 8 candy leftover.
• Those 11 evolutions give you 11 more candies, for a total of 19 candy.
• Transferring the 11 pidgeotto you evolved gives you 11 more candies, for a total of 30 candy.
• Repeat the process with the 30 candy.
  • You could use 24 of those candies to evolve 2 pidgeys (2*12=24) leaving you with 6 candy leftover.
  • Those 2 evolutions give you 2 more candies, for a total of 8 candy.
  • Transferring the 2 pidgeotto you evolved gives you 2 more candies, for a total of 10 candy.
  • 10 candy is not enough to evolve, so that's it for evolution! But if there were 12 or more we'd repeat the process.

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. If you like your recursive program can evolve one pidgey at a time, which is easier to write, but not as efficient as evolving a greater number at a time.

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 kjmock@alaska.edu by midnight for lab credit.