Transcript ppt

Examples of Recursion
Instructor: Mainak Chaudhuri
[email protected]
1
Sum of natural numbers
class SumOfNaturalNumbers {
public static void main (String arg[]) {
int m = 3, n = 10;
if (m > n) {
System.out.println (“Invalid input!”);
}
else {
System.out.println (“Sum of numbers from ”
+ m + “ to ” + n + “ is ” + Sum(m, n));
}
2
}
Sum of natural numbers
public static int Sum (int m, int n) {
int x, y;
if (m==n) return m;
x = Sum(m, (m+n)/2);
y = Sum((m+n)/2+1, n);
return (x+y);
}
} // end class
3
GCD revisited
• Recall that gcd (a, b) = gcd (a-b, b)
assuming a > b.
– Directly defines a recurrence
public static int gcd (int a, int b) {
if ((a==1) || (b==1)) return 1;
if (a==b) return a;
if (a < b) return gcd (a, b-a);
if (a > b) return gcd (a-b, b);
}
4
GCD revisited
• Refinement: gcd (a, b) = gcd (a-nb, b) for
any positive integer n such that a >= nb,
in particular n = a/b, assuming a > b
public static int gcd (int a, int b) {
if (0==a) return b;
if (0==b) return a;
if (a < b) return gcd (a, b%a);
if (a > b) return gcd (a%b, b);
}
5
Towers of Hanoi
• Three pegs, one with n disks of
decreasing diameter; two other pegs are
empty
• Task: move all disks to the third peg
under the following constraints
– Can move only the topmost disk from one peg
to another in one step
– Cannot place a smaller disk below a larger
one
• An example where recursion is much
easier to formulate than a loop-based
solution
6
Towers of Hanoi
• We want to write a recursive method
THanoi (n, 1, 2, 3) which moves n disks
from peg 1 to peg 3 using peg 2 for
intermediate transfers
• The first step is to formulate the
algorithm
– Observation: THanoi (n, 1, 2, 3) Ξ THanoi (n1, 1, 3, 2) followed by transferring the
largest disk to peg 3 from peg 1 and calling
THanoi (n-1, 2, 1, 3)
– Stopping condition: n = 1
7
Towers of Hanoi
class TowersOfHanoi {
public static void main (String arg[]) {
int n = 10;
THanoi(n, 1, 2, 3);
}
8
Towers of Hanoi
public static void THanoi (int n, int source, int
extra, int destination) {
if (n > 1) {
THanoi (n-1, source, destination, extra);
}
System.out.println (“Move disk ” + n + “ from
peg ” + source + “ to peg ” + destination);
if (n > 1) {
THanoi (n-1, extra, source, destination);
}
} // How many moves needed? 2n-1
} // end class
9
Towers of Hanoi
• Total number of method calls
Let Tn be the number of method calls to solve
for n disks
Tn = 2Tn-1 + 1 for n > 1; T1 = 1
– Use generating function to solve the
recurrence (worked out in class on board)
10
Fibonacci series
• Number of method calls
– Refer to the program in the last lecture
– Let Tn be the number of method calls to find
the nth Fibonacci number
Tn = Tn-1 + Tn-2 + 1 for n > 2; T1 = T2 = 1
– Use generating function to solve the
recurrence
– Observe that Tn = Fn – 1 where Fn is the nth
Fibonacci number
Tn = (21-n/√5)((1+√5)n – (1-√5)n) – 1
– The number (1+√5)/2 is called the golden
11
ratio, which is lim n￫∞ (Fn+1/Fn)