Problem 9
Find out how often the recursive version of the fib function calls itself. Keep a global variable fibcount and increment it once in every call to \(\mathrm{fib}\). What is the relationship between \(f i b(n)\) and fibcount?
Problem 9
Using recursion, compute the sum of all values in a list.
Problem 11
The following function was known to the ancient Grecks for computing square roots. Given a value \(x>0\) and a guess \(g\) for the square root, a better guess is \((g+x / g) / 2 .\) Write a recursive helper function def squareRoottuess \((x, 9)\). If \(g^{2}\) is approximately equal to \(x\), return \(g\), otherwise, return squareRootCuess with the better guess. Then write a function def squareRoot \((x)\) that uses the helper function.
Problem 17
Implement an iterator that produces the moves for the Towers of Hanoi puzzle described in Worked Example 11.2. Provide methods hasMorexoves and nexthove. The nextNove method should yield a string describing the next move. For example, the following code prints all moves needed to move five disks from peg 1 to peg 3 : nover = DiskNover \((5,1,3)\) while mover.hasMoreMoves \(\mathrm{O}\) : print (nover. nextMove(O) Hint: A disk mover that moves a single disk from one peg to another simply has a nextMove method that returns a string Move disk from peg sotree to target A disk mover with more than one disk to move must work harder. It needs another Disklover to help it move the first \(d-1\) disks. The nextrove asks that disk mover for its next move until it is done. Then the nextmove method issues a command to move the \(d\) th disk. Finally, it constructs another disk mover that generates the remaining moves. It helps to keep track of the state of the disk mover: \- BEFORE LARCEST: A helper mover moves the smaller pile to the other peg. \- LARCEST: Move the largest disk from the source to the destination. \- Arter LARCEST: The helper mover moves the smaller pile from the other peg to the target. \- DONE: All moves are done.
Problem 21
Refine the program for solving the eight queens problem so that rotations and reflections of previously displayed solutions are not shown. Your program should display twelve unique solutions.
Problem 22
Refine the program for solving the cight queens problem so that the solutions are written to an HTML. file, using tables with black and white background for the board and the Unicode character " " "lu2655" for the queen.
Problem 23
Generalize the program for solving the eight queens problem to the \(n\) queens problem. Your program should prompt for the value of \(n\) and display the solutions.
Problem 24
Using backtracking, write a program that solves summation puzzles in which each letter should be replaced by a digit, such as send + more = money Other examples are base + ba11 - ganes and kyoto + osaka - tokyo.
Problem 25
The recursive computation of Fibonacci numbers can be specded up significantly by keeping track of the values that have already been computed. Provide an implementation of the fib function that uses this strategy. Whenever you return a new valuc, also store it in an auxiliary list. However, before cmbarking on a computation, consult the list to find whether the result has already been computed. Compare the running time of your improved implementation with that of the original recursive implementation and the loop implementation.
