static int sum(int n) {
}
Let's trace the method calls:
How is this implemented in the computer?
Makes use of the run-time Stack
For each method call an "activation record" is pushed onto the stack:
1. method parameters
2. local variables
3. return address
Pretend return value is on stack - probably in a register
return value return value
sum(1) 1
sum(2) 2 + sum(1)
sum(3) 3 + sum(2)
sum(4) 4 + sum(3)
main() System.out.println(sum(4));
Factorials are recursively defined as
Base case 0! = 1 (the text is incorrect in saying
that factorials are only defined
for "positive" integers)
Recursive rule n! = n * n-1!
Write an iterative and recursive version of a method that returns n!
You should use a long integer for both the parameter and the return
type since factorials can quickly exceed the largest possible integer
value. The long type is needed to represent factorials > 12! 479001600
long can only be used to represent values up to
20! 2432902008176640000
Biggest int - 4 bytes - ~2 billion
Biggest long - 8 bytes - 19 digits 9........
static long factorial(long n) {
}
static long factorial(long n) {
}
csc% java Factorial
n = 0 factorial = 1
n = 1 factorial = 1
n = 2 factorial = 2
n = 3 factorial = 6
n = 4 factorial = 24
n = 5 factorial = 120
n = 6 factorial = 720
n = 7 factorial = 5040
n = 8 factorial = 40320
n = 9 factorial = 362880
n = 10 factorial = 3628800
n = 11 factorial = 39916800
n = 12 factorial = 479001600
n = 13 factorial = 6227020800
n = 14 factorial = 87178291200
n = 15 factorial = 1307674368000
n = 16 factorial = 20922789888000
n = 17 factorial = 355687428096000
n = 18 factorial = 6402373705728000
n = 19 factorial = 121645100408832000
n = 20 factorial = 2432902008176640000
Write an iterative and recursive version of a method that returns
xn power
where n >= 0
Base case x0 = 1 (even if x == 0 according to Math.pow(0,0))
Recursive rule xn = x * xn-1
static long power(long x, long n) {
}
static long power(long x, long n) {
}
Write iterative and recursive methods to search for a value in an
integer array.
static boolean search(int[] array, int value) {
}
static boolean search(int[] array, int size, int value) {
}
Fibonacci Sequence
------------------
Start with 1 pair of rabbits at the beginning of month 1.
They will produce a pair of rabbits during the 2nd month so at
the beginning of the third month there will be 2 pairs of
rabbits.
The fibonacci sequence has two base cases and one recursive rule:
Base cases - fib(1) = 1, fib(2) = 1
Recursive rule - fib(n) = fib(n-1) + fib(n-2)
Write iterative and recursive methods to calcualate the nth
Fibonacci number.
//Methods assume n > 0 - Note that fib(0) is defined to be 0
public static int fib(int n) {
if (n == 1)
return 1;
if (n == 2)
return 1;
int prevPrev = 1;
int prev = 1;
int curr = 0; //Initialize current value so compiler
//won't complain!
for (int i = 3; i <= n; i++) {
curr = prev + prevPrev;
prevPrev = prev;
prev = curr;
}
return curr;
}
public static int recursiveFib(int n) {
}
Actually using recursion to calculate fibonacci numbers, while simpler
and more elegant than iterations is EXTREMELY inefficient - the number
of method calls grows exponentially!! The number of method calls to
calculate the nth Fibonacci number is about 2^n. Thus calculating the
20th Fibonacci number requires about 2^20 or about 1,000,000
method calls.
Let's compare the "recursion tree" for calculating factorials
and fibonacci numbers:
Number of method calls to calculate 5! _____
Number of method calls to calculate n! _____
Number of method calls to calculate fib(5) ______
fib(4) ______
fib(3) ______
fib(2) ______
fib(1) _____
To calculate fib(6) -
1 + # of calls for fib(5)+ # of calls for fib(4) = _______
Towers of Hanoi
---------------
"Every budding computer scientist must grapple with certain classic
problems and the Towers of Hanoi is one of the most famous of these.
Legend has it tat in a temple in the Far East, priests are attempting
to move a stack of disks from one peg to another. The initial stack
had 64 disks threaded onto one peg and arranged from bottom to top by
decreasing size. The priests are attempting to move the stack from
this peg to another peg under the constraints that exactly one disk
is moved at a time and at no time may a larger disk be placed on top
of a smaller disk. a third peg is available for temporarily holding
disks. Supposedly, the world will end when the priests complete
their task, so there is little incentive for us to facilitate their
efforts."
It can be proven that moving n disks from peg 1 to peg 3 following the
given rules requires at least 2^n - moves. So to move
1 disk: 2^1 - 1 = 1 move
2 disks: 2^2 - 1 = 3 moves
3 disks: 2^3 - 1 = 7 moves
4 disks: 2^4 - 1 = 15 moves
.
.
.
64 disks: 2^64 - 1 = 18,446,744,073,709,551,615.
So if it took the priests 1 minute to make each move, it would take
them about 30 trillion years to move all 64 pegs.
"A game called the Tower of Hanoi patterned after this legend was
invented by French mathematician, Edouard Lucas(1842 - 1891). It
consisted of a board with three upright pegs and seven disks."
Foundations of Discrete Mathematics by Peter Fletcher, et. al.
Let's try solving the problem for 1, 2, 3, and 4 disks.
Then we'll look at the code for solving it recursively which
is surprisingly simple:
OUTPUT:
TOWERS OF HANOI for 1 disk(s)
1 --> 3
TOWERS OF HANOI for 2 disk(s)
1 --> 2
1 --> 3
2 --> 3
TOWERS OF HANOI for 3 disk(s)
1 --> 3
1 --> 2
3 --> 2
1 --> 3
2 --> 1
2 --> 3
1 --> 3
TOWERS OF HANOI for 4 disk(s)
1 --> 2
1 --> 3
2 --> 3
1 --> 2
3 --> 1
3 --> 2
1 --> 2
1 --> 3
2 --> 3
2 --> 1
3 --> 1
2 --> 3
1 --> 2
1 --> 3
2 --> 3
//Hanoi.java - modified from Deitel & Deitel Java How to Program
// solution
//Suzanne Balik, 4 Oct 2001
public class Hanoi {
public static void tower(int disks, int peg1, int peg3, int peg2) {
if (disks == 1) {
System.out.println(peg1 + " --> " + peg3);
return;
}
//Move all disks but bottom disk from peg1 to peg2
tower (disks - 1, peg1, peg2, peg3);
//Move bottom disk from peg1 to peg3
System.out.println(peg1 + " --> " + peg3);
//Move all disks but bottom disk from peg2 to peg3
tower(disks - 1, peg2, peg3, peg1);
}
public static void main(String[] args) {
final int MAX = 4;
for (int i = 1; i <= MAX; i++) {
System.out.println("\nTOWERS OF HANOI for " + i + " disk(s)\n");
tower(i, 1, 3, 2);
}
}
}