# 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 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 that were 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.

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