Recursion

 
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 
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);
    }
  }
  
}