Week 6 (Recursion)

Watch video (Recursion)

1. Have a look at the Hope Tutorial. Also see these notes
2. Play with Hope on igor: Log on to igor and type hope

   Type in some simple expressions at the Hope prompt >: like:

   1;
   1+1;
   'a';
   true and false;
   

3. Try out the factorial function:

   factorial: num -> num;
   factorial(0) <= 1;
   factorial(n+1) <= (n+1)*factorial(n);
   

   Use is to work out factorial of five, ten and twenty.

4. Write factorial in Java. solution

5. Write Fibonacci in Java.

   fib: num -> num;
   fib(n) <= if (n<2) then 1 else fib(n-1) + fib(n-2);
   

   solution

6. multiplication can be defined in terms of addition as follows:

   mult: num # num -> num;
   mult(0,m) <= 0;
   mult(n+1,m) <= m+ mult(n,m);
   

   Define mult in Java. solution

7. (Easy Assignment) The greatest common divisor of two numbers can be defined as follows:

   gcd: num # num -> num;
   gcd(n,m) <= if (n=m) then n
               else if n>m 
   	         then gcd(n-m,m)
   		 else gcd(m,m-n);
   

   Program this in Java.

8. Study the following Java class: (Watch video (Recursive Generic List Methods))

   import java.util.*;
   public class genericLists  <T>
   {
   	public  T head (ArrayList  <T> m)
   	{
   			return m.get(0);
   	}
   	
   	public  ArrayList <T>  tail (ArrayList <T>  t)
   	{	
   		ArrayList <T> m= new ArrayList <T> (t);
   		m.remove(0);	
   		return m;
   	}
   	
   	public  ArrayList <T>  nil ()
   	{
   			return new ArrayList <T>();
   	}
   	
   	public  ArrayList  <T> cons (T t, ArrayList <T> m)
   	{	
   		ArrayList <T> k= new ArrayList <T>();
   		k.add(t);
   		k.addAll(m);
   		return k;
   	}
   	
   	public  ArrayList <T> append (ArrayList <T>  t, ArrayList <T>  u)
   	{	
   		if (t.isEmpty()) return u;
   		else return cons(head(t),append(tail(t),u));
   	}
   
   	public 	 ArrayList <T> reverse (ArrayList <T>  t)
   	{	
   		if  (t.isEmpty()) return t;
   		else return append(reverse(tail(t)),cons(head(t),new ArrayList <T>()));
   	}
   }
   

   Watch video (Write recursive methods using the basic Generic List Methods))

9. Write a recursive function, makeR which give an integer n returns the ArrayList [n,n-1,...,0] for all non-negative n. makeR(n) returns the list produced by makeR(n-1) and then adding n to the beginning of the list. solution

10. Write a recursive function, makeL which give an integer n returns the ArrayList [0,1,...,n] for all non-negative n. makeL(n) returns the list produced by makeL(n-1) and then adding n to the end of the list. solution

11. Consider the following function in hope

    makebetween: num # num -> list(num);
    makebetween (n,m) <= if (n=m) then [n] else n::makebetween(n+1,m);
    

    Program this in Java. solution

12. Try out the following hope function:

    reverse: list(alpha) -> list(alpha);
    reverse(nil) <= nil;
    reverse(x::l) <= reverse(l) <> [x];
    
    revrev: list(list(alpha)) -> list(list(alpha));
    revrev(nil) <= nil;
    revrev(x::l) <= revrev(l) <> [reverse(x)];
    

    try: e.g.

    revrev[[1,2.3],[4,5,6]];
    

    Program revrev in Java. solution

13. (Hard Assignment) (Watch video (Help with hard assignment))

    To Sort a list of integers into descending order, if it's empty return the empty list otherwise sort the tail and inser the head in the right place.

    Here is the solution in Hope:

    insert: num # list(num) -> list(num);
    insert(x,nil) <= [x];
    insert (x,y::m) <= if (x<y) then y::insert(x,m)
    			   else  x::(y::m);
    			   
    sort: list(num) -> list(num);
    sort(nil) <= nil;
    sort(x::m) <= insert(x,sort(m));
    

    Try it out!

    Complete this Java program to sort a list into ascending order:

    import java.util.*;
    
    public class sort
    {
    	static genericLists <Integer> L = new genericLists <Integer>();
    	
    	static  ArrayList  <Integer> insertAscending (Integer x, ArrayList <Integer> l)
    	{
    		
    	
    	}		
    	
    	
    	static ArrayList <Integer> sortAscending (ArrayList <Integer> l)
    	{		
    	}
    	
    	public static void main(String [] args)
    	{
    	
    		System.out.println((maker.makeR(Integer.parseInt(args[0])))); //use your makeR method from before.
    	
    		System.out.println(sortAscending(maker.makeR(Integer.parseInt(args[0]))));
    	
    	}
    
    }
    

    solution

    Week 3 Resources