How do we write a loop to calculate the sum of the first n numbers where n >= 1? //Precondition: //Postcondition: static int sum(int n) { } OR static int sum(int n) { } How can we use recursion (a method calling itself) to do the same thing? First lets compare two ways of adding up the numbers by hand: We can write a method that calls itself recursively to calculate the sum of the first n numbers in this way:

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 x^{n}power where n >= 0 Base case x^{0}= 1 (even if x == 0 according to Math.pow(0,0)) Recursive rule x^{n}= x * x^{n-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); } } }