For this program you'll write a program that uses a recursive function to carry out a depth-first search in C++.

The Teddy Bear Game is played as follows:

You start the game with N teddy bears, 0 < N <= 10,000. You may ask for or give back teddy bears according to these rules: If the number of teddy bears you have is an even number, you can turn in (remove) exactly half the teddy bears you have. If the number of teddy bears you have is a multiple of 3, you can ask for (receive) one third as many teddy bears as you currently have. (So if you have 33, you can ask for another 11.) You can always ask for (receive) exactly 23 teddy bears. There is no priority among the rules; you may choose any rule that applies in a given situation. The number of teddy bears you hold must always be greater than 0 and can never be more than 10,000. The object of the game is to end with exactly 17 teddy bears in no more than 20 moves. Your program will ask the user for the starting number of teddy bears, and then use a recursive function to search for a solution. Your program must use recursion to receive full credit. Output for each case is either a statement that no solution within 20 moves exists (determined after exhaustive search) or a listing of what choices are necessary to end with exactly 17. Because you're using a recursive function, it may be simpler to list it from the last step going backwards towards the beginning; that's fine. Allow the user to enter multiple values for N. If the user enters values out of range, prompt for reentry. Ask the user after each case whether to continue.

Sample Session:

How many bears are you starting with? 134 Searching for a solution within 20 moves.... Found solution. I have exactly 17 bears, with 6 moves left. Reduce 34 by half to get 17. Reduce 68 by half to get 34. With 51, add 1/3 to get 68. With 28, add 23 to get 51. With 5, add 23 to get 28. Reduce 10 by half to get 5. Reduce 20 by half to get 10. With 15, add 1/3 to get 20. Reduce 30 by half to get 15. Reduce 60 by half to get 30. With 45, add 1/3 to get 60. Reduce 90 by half to get 45. With 67, add 23 to get 90. Reduce 134 by half to get 67. Would you like to try again [Y/N]?