Defining sequences recursively... Tower of Hanoi Poles in a Circle: Suppose that

Question

Defining sequences recursively... Tower of Hanoi Poles in a Circle: Suppose that instead of being lined up in a row, the three poles for the original Tower of Hanoi are placed in a circle. The monks move the disks one by one from one pole to another, but they may only move disks one over in a clockwise direction and they may never move a larger disk on top of a smaller one. Let c sub n be the minimum number of moves needed to transfer a pile of n disks from one pole to the next adjacent pole in the clockwise direction. a) Justify the inequality c sub k <= c sub (k-1) +1 for all integers k>2... b)The expression 4c sub (k-1) +1 is not the minimum number of moves needed to transfer a pile of k disks from one pole to another. Explain, for example, why c sub 3 DNE c sub 2 +1

Explanation / Answer

The idea of calling one function from another immediately suggests the possibility of a function calling itself. The function-call mechanism in Java supports this possibility, which is known as recursion. Recursion is a powerful general-purpose programming technique, and is the key to numerous critically important computational applications, ranging from combinatorial search and sorting methods methods that provide basic support for information processing (Chapter 4) to the Fast Fourier Transform for signal processing (Chapter 9). Your first recursive program. The HelloWorld for recursion is to implement the factorial function, which is defined for positive integers N by the equation N! = N × (N-1) × (N-2) × ... × 2 × 1 N! is easy to compute with a for loop, but an even easier method in Factorial.java is to use the following recursive function: public static int factorial(int N) { if (N == 1) return 1; return N * factorial(N-1); } You can persuade yourself that it produces the desired result by noting that factorial() returns 1 = 1! when N is 1 and that if it properly computes the value (N-1)! = (N-1) × (N-2) × ... × 2 × 1 then it properly computes the value N! = N × (N-1)! = N × (N-1) × (N-2) × ... × 2 × 1 We can trace this computation in the same way that we trace any sequence of function calls. factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 120 Our factorial() implementation exhibits the two main components that are required for every recursive function. The base case returns a value without making any subsequent recursive calls. It does this for one or more special input values for which the function can be evaluated without recursion. For factorial(), the base case is N = 1. The reduction step is the central part of a recursive function. It relates the function at one (or more) inputs to the function evaluated at one (or more) other inputs. Furthermore, the sequence of parameter values must converge to the base case. For factorial(), the reduction step is N * factorial(N-1) and N decreases by one for each call, so the sequence of parameter values converges to the base case of N = 1. Mathematical induction. Recursive programming is directly related to mathematical induction, a technique for proving facts about discrete functions. Proving that a statement involving an integer N is true for infinitely many values of N by mathematical induction involves two steps. The base case is to prove the statement true for some specific value or values of N (usually 0 or 1). The induction step is the central part of the proof. For example, we typically assume that a statement is true for all positive integers less than N, then use that fact to prove it true for N. Such a proof suffices to show that the statement is true for all N: we can start at the base case, and use our proof to establish that the statement is true for each larger value of N, one by one. Euclid's algorithm. The greatest common divisor (gcd) of two positive integers is the largest integer that divides evenly into both of them. For example, the greatest common divisor of 102 and 68 is 34 since both 102 and 68 are multiples of 34, but no integer larger than 34 divides evenly into 102 and 68. We can efficiently compute the gcd using the following property, which holds for positive integers p and q: If p > q, the gcd of p and q is the same as the gcd of q and p % q. The static method gcd() in Euclid.java is a compact recursive function whose reduction step is based on this property. gcd(1440, 408) gcd(408, 216) gcd(216, 192) gcd(192, 24) gcd(24, 0) return 24 return 24 return 24 return 24 return 24 Towers of Hanoi. No discussion of recursion would be complete without the ancient towers of Hanoi problem. We have three poles and n discs that fit onto the poles. The discs differ in size and are initially arranged on one of the poles, in order from largest (disc n) at the bottom to smallest (disc 1) at the top. The task is to move the stack of discs to another pole, while obeying the following rules: Move only one disc at a time. Never place a disc on a smaller one. To solve the problem, our goal is to issue a sequence of instructions for moving the discs. We assume that the poles are arranged in a row, and that each instruction to move a disc specifies its number and whether to move it left or right. If a disc is on the left pole, an instruction to move left means to wrap to the right pole; if a disc is on the right pole, an instruction to move right means to wrap to the left pole. Exponential time. One legend says that the world will end when a certain group of monks solve the Towers of Hanoi problem in a temple with 64 golden discs on three diamond needles. We can estimate the amount of time until the end of the world (assuming that the legend is true). If we define the function T(n) to be the number of move directives issued by TowersOfHanoi.java to move n discs from one peg to another, then the recursive code implies that T(n) must satisfy the following equation: T(n) = 2 T(n - 1) + 1 for n > 1, with T(1) = 1 Such an equation is known in discrete mathematics as a recurrence relation. We can often use them to derive a closed-form expression for the quantity of interest. For example, T(1) = 1, T(2) = 3, T(3) = 7, and T(4) = 15. In general, T(n) = 2^n - 1. Knowing the value of T(n), we can estimate the amount of time required to perform all the moves. If the monks move discs at the rate of one per second, it would take more than one week for them to finish a 20-disc problem, more than 31 years to finish a 30-disc problem, and more than 348 centuries for them to finish a 40-disc problem (assuming that they do not make a mistake). The 64-disc problem would take more than 5.8 billion centuries......................

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.