Agenda#

The object of this practical is for you to practice the technique of recursion.

Exercise 1 - Calculating Exponents using Recursion#

Raising a number to a power, an exponent, such as $y$ to the power 2 ($y$ squared), is written with circumflex (^) in some notations and as ** in others. So $y$ squared, $y^2$, is written y^2 or y ** 2. When we write $y^n$ we mean $y$ to the power $n$.

Using the facts that $y^0 = 1$ and $y^n = y \times y^{n-1}$, for $n > 0$, write a recursive method (that does not use the ^ operator)

1
public static double power(double y, int n) {
2
// pre: n >= 0
3
// post: the value returned is y^n
4
}

What is the base case of a recursive method? What is the recursive case?

Specifically, what are the base case(s) and recursive case(s) of the code from part (a)?

Exercise 2 - Getting some practice code set up#

Download the supplied code files from the student website and get them up and running as a project as usual. The main file is RecursionPractice.java.

Add the code of the method from Exercise 1, and try it out on various values by inserting into the main method lines such as:

1
System.out.println("2 to the power 5 is " + power(2,5));

1
public static int power(int y, int n) {
2
  // pre: n >= 0
3
  // post: the value returned is y^n
4
  if (n == 0) {
5
    return 1;
6
  } else {
7
    return y * power(y, n - 1);
8
  }
9
}

Exercise 3 - Chessboard squares#

Write a recursive method, which does not use multiplication , which given a positive integer $n$, calculates how many $1 \times 1$ squares there are on a $n \times n$ chessboard :

1
public static int chessBoardSquares(int n) {
2
// pre: n >= 1
3
// post: the result is the number of squares on an n × n chessboard
4
}

For example, chessBoardSquares(5) should return the value 25. Test your method by adding code like the following to your main method:

1
for (int i = 1; i <= 8; i++) {
2
    System.out.println("chessBoardSquares(i) for i = " + i + " is " + chessBoardSquares(i));
3
}

Hints:

1. Use recursion on $n$, and have your base case be $n = 1$.

2. For the recursive case, draw a $n \times n$ chessboard, and then identify where inside that you can see a $(n − 1) \times (n − 1)$ chessboard.

3. See also extra ‘hint’ here:
   

1
public static int chessBoardSquares(int n) {
2
    // pre: n >= 1
3
    // post: the result is the number of 1x1 squares on an n × n chessboard
4
    if (n == 1) {
5
        return 1;
6
    }
7
    return chessBoardSquares(n - 1) + (2 * n - 1);
8
}

Exercise 4 - Array Matching#

Write a recursive method that returns true precisely when the first $n$ integers of two given arrays of integers are the same.

1
public static boolean arrayMatch(int n, int[] a, int[] b) {
2
// pre: 0 <= n <= a.length and 0 <= n <= b.length
3
// post: true is returned precisely when the values
4
//   a[0] ... a[n-1] are exactly the same as
5
//   the values b[0] ... b[n-1]
6
}

Test your method with some code such as this in the main method:

1
int[] a = {1, 2, 3, 4, 5, 6};
2
int[] b = {1, 2, 4, 8, 16};
3
for (int i = 1; i <= 5; i++)
4
    System.out.println("arrayMatch(i, a, b) for i = " + i + " is " + arrayMatch(i,a,b));

Hints:

1. Use recursion on $n$, and have your base case be $n = 0$

2. For the recursive case, draw a diagram of the two arrays indicating where the first $n$ elements are. Draw also a diagram of the two arrays indicating where the first $n-1$ elements are. Ask yourself: how can the result from comparing the first $n-1$ items be used to compare the first $n$ items? Look at the difference between the diagrams.

1
public static boolean arrayMatch(int n, int[] a, int[] b) {
2
  // pre: 0 <= n <= a.length and 0 <= n <= b.length
3
  // post: true is returned precisely when the values
4
  //   a[0] ... a[n-1] are exactly the same as
5
  //   the values b[0] ... b[n-1]
6
  if (n == 0) {
7
    return true;
8
  }
9
  if (a[n - 1] != b[n - 1]) {
10
    return false;
11
  }
12
  return arrayMatch(n - 1, a, b);
13
}

1
public static boolean arrayMatch2(int n, int[] a, int[] b) {
2
  if (n == 0) {
3
    return true;
4
  }
5
  return a[n - 1] == b[n - 1] && arrayMatch2(n - 1, a, b);
6
}

Exercise 5 - Triangle numbers#

Write a recursive method, which, given an integer $n$, calculates the sum of the integers from $1$ to $n$:

1
public static int triangle(int n) {
2
// pre: n >= 1
3
// post: the result is the sum 1 + 2 + ... + n
4
}

Hint: use recursion on $n$, and have your base case be $n = 1$.

Test your method by some code such as the following in your main method:

1
for (int i = 1; i <= 10; i++)
2
    System.out.println("Triangle number " + i + " is " + triangle(i));

1
public static int triangleNumber(int i) {
2
  // pre: n >= 1
3
  // post: the result is the sum 1 + 2 + ... + n
4
  if (i == 1) {
5
    return 1;
6
  }
7
  return triangleNumber(i - 1) + i;
8
}

Exercise 6 - Array printing#

Write a recursive method, to print out (using a System.out.println statement) all the contents of an array from positions $0$ to $n-1$:

1
public static void printFirstN(String[] a, int n) {
2
// pre: 0 <= n <= a.length
3
// post: the values a[0] ... a[n-1] are printed on the screen
4
}

Test your method with some code such as the following in the main method:

1
String[] a = {"Red", "Yellow", "Pink", "Green", "Orange"};
2
printFirstN(a, a.length);

1
public static void printFirstN(String[] a, int n) {
2
  // pre: 0 <= n <= a.length
3
  // post: the values a[0] ... a[n-1] are printed on the screen
4
  if (n == 0) {
5
    return;
6
  }
7
  printFirstN(a, n - 1);
8
  System.out.println(a[n - 1]);
9
}

1
public static void printFirstN2(String[] a, int n) {
2
  if (n != 0) {
3
    System.out.println(a[n - 1]);
4
    printFirstN2(a, n - 1);
5
  }
6
}

Java Visualizer#

Exercise 1#

Go to the java visualizer tool at https://cscircles.cemc.uwaterloo.ca/java_visualize/ then run the example from the lecture slides and observe what happens on the call stack. The code for the relevant methods is:

1
public static void main(String[] args) {
2
    double answer = getAverage(2,3);
3
    System.out.println(answer);
4
}
5

6
public static double getAverage(double x, double y){
7
    double average = getSum(x,y)/2;
8
    return average;
9
}
10

11
public static double getSum(double x, double y) {
12
    double sum = x+y;
13
    return sum;
14
}

Exercise 2#

Use the visualizer tool to run the ‘reverse’ example from the lecture slides. The code for the reverse method is:

1
public static void reverse(ArrayList<String> a) {
2
    if (a.size() > 1) {
3
        String s = a.remove(0);
4
        reverse(a);
5
        a.add(s);
6
    }
7
}

You will need to create a main method that creates an ArrayList, adds some values to it, and then calls the reverse method. You will also need to import java.util.ArrayList.

1
import java.util.ArrayList;
2

3
public class ReverseArrayListDemo {
4
    // 递归反转ArrayList<String>的核心方法
5
    public static void reverse(ArrayList<String> a) {
6
        if (a.size() > 1) {
7
            // 移除并获取第一个元素
8
            String s = a.remove(0);
9
            // 递归反转剩余元素
10
            reverse(a);
11
            // 将移除的元素添加到列表末尾
12
            a.add(s);
13
        }
14
    }
15

16
    // 主方法：测试反转逻辑
17
    public static void main(String[] args) {
18
        // 1. 创建并初始化ArrayList
19
        ArrayList<String> list = new ArrayList<>();
20
        list.add("A");
21
        list.add("B");
22
        list.add("C");
23
        list.add("D");
24

25
        // 2. 输出反转前的列表
26
        System.out.println("反转前: " + list);
27

28
        // 3. 调用递归反转方法
29
        reverse(list);
30

31
        // 4. 输出反转后的列表
32
        System.out.println("反转后: " + list);
33
    }
34
}

Exercise 3#

Make a Java project from the source file Anagram.java and run it with some short strings as parameter. Using the visualizer or otherwise try to understand how the recursion is working.

1
package anagrams;
2
import java.util.*;
3
public class Anagrams {
4
    private static void recursivePermute(char[] sa, int start) {
5
        int len = sa.length;
6
        if (start == len) System.out.println(sa);
7
        else {
8
            for (int i = start; i < len; i++) {
9
                char temp = sa[start];
10
                sa[start] = sa[i];
11
                sa[i] = temp;
12
                recursivePermute(sa, start + 1);
13
                sa[i] = sa[start];
14
                sa[start] = temp;
15
            } // for
16
        } // if
17
    } // recursivePermute
18

19
    private static void permuteString(String s) {
20
        char[] sa = new char[s.length()];
21
        for (int i = 0; i < s.length(); i++) sa[i] = s.charAt(i);
22
        recursivePermute(sa, 0);
23
    }
24

25
    public static void main(String[] args) {
26
        System.out.print("String to permute? ");
27
        Scanner keyboard = new Scanner(System.in);
28
        String initial = keyboard.next();
29
        permuteString(initial);
30
    }
31
}

Exercise 4#

Make a Java project from the source file EightQuuens.java and run it. Using the visualizer or otherwise try to understand how the recursion is working.

1
package eightQueens;
2
/**
3
 * from Algorithms and Data Structures page 97
4
 * © N. Wirth 1985 (Oberon version: August 2004)
5
 * Translated into Java and corrected
6
 */
7
public class EightQueens {
8
    static int[] x = new int[8];
9
    static boolean[] a = new boolean[8];
10
    static boolean[] b = new boolean[15];
11
    static boolean[] c = new boolean[15];
12
    // x[i] is position of queen in i th column
13
    // a[j] means "no queen lies on j th row"
14
    // b[k] means "no queen occupies k th /-diagonal"
15
    // c[k] means "no queen occupies k th \-diagonal"
16
    // in /-diagonal k is i+j
17
    // in \-diagonal k is i-j+7
18

19
    public static void writeIt() {
20
        for (int k = 0; k <= 7; k++) {
21
            System.out.print(" " + x[k]);
22
        }
23
        System.out.println();
24
    } // end writeIt
25

26
    public static void tryIt(int i) {
27
        for (int j = 0; j <= 7; j++) { // corrected from Oberon version
28
            if (a[j] && b[i + j] && c[i - j + 7]) {
29
                x[i] = j;
30
                a[j] = false; b[i + j] = false; c[i - j + 7] = false;
31
                if (i < 7)
32
                    tryIt(i + 1);
33
                 else
34
                    writeIt();
35
                a[j] = true; b[i + j] = true; c[i - j + 7] = true;
36
            }
37
        }
38
    } // end tryIt
39

40
    public static void main(String[] args) {
41
        for (int i = 0; i <= 7; i++) a[i] = true;
42
        for (int i = 0; i <= 14; i++) {
43
            b[i] = true; c[i] = true;
44
        }
45
        tryIt(0);
46
    }
47
}

Exercise 5#

Make a Java project from the source file Ackermann.java and run it. Using the visualizer or otherwise try to understand how the recursion is working.

1
package ackermann;
2
public class Ackermann {
3
    public static int A (int m, int n){
4
    System.out.println("Calling A, m = " + m + " n = " + n);
5
    int result = 0;
6
    if (m == 0) result = n + 1;
7
    else if (m > 0 && n == 0) result = A(m-1, 1);
8
    else if (m > 0 && n > 0) result = A(m-1, A(m, n-1));
9
    System.out.println("Returning " + result);
10
    return result;
11
}
12

13
    public static void main(String[] args) {
14
        System.out.println(A(4, 2));
15
    }
16
}