Content#

• Recursion
  • What is recursion
  • What it is good for
  • When not to use recursion
  • Backtracking

Basic concepts about Recursion#

• Self-referential (defined in terms of itself)

• Natural numbers:

  • a) 1 is a natural number
  • b) The successor of a natural number is a natural number

• Recursion is a programming technique much used in declarative (functional) programming -a different way of getting repetition.

Recursive pattern: Fractals#

Koch snowflake	the Barnsley fern
Shapes made of smaller versions of self	Not a photo, It is generated by a mathematical formula

Factorial function#

• Factorial 5, written 5!, is:
  • $5\times4\times3\times2\times1$
• and 6! is
  • $6\times5\times4\times3\times2\times1$, so $6\times5!$

⬇

Factorial function, for non-negative integers is:

• a) $0! = 1$
• b) if $n > 0$, then $n! = n\times(n - 1)!$

Factorial function in Java#

1
int factorial (int n) {
2
/*  pre: n >= 0
3
    post: factorial(n) = n!  */
4
    if (n == 0) then return 1;
5
    else return n * factorial(n - 1);
6
} /* factorial */

This function has problem:

Infinite recursion (silly)#

1
void TellStory() {
2
    System.out.println("It was a dark and stormy night");
3
    System.out.println("and the captain said to the mate");
4
    System.out.println(" 'Tell us a story mate' ");
5
    System.out.println("and this is the story he told … ");
6
    TellStory();
7
} /* TellStory */

This function has problem:

Useful recursion#

• To be useful the recursion must terminate, so there must be
  • at least one non-recursive, base case (in factorial, it is 0!)
  • as well as recursive cases.

Other recursive examples#

• A linked list is:

  • a) empty, or
  • b) has a head (first element)
    and a tail, which is a linked list

• A tree is:

  • a) empty, or
  • b) has a root,
    and left (sub-) tree and right (sub-) tree

A Recursive Class-Linked lists#

1
public class Node {
2
    public String data;
3
    public Node next;
4
    // Here’s the recursive bit! One of the fields of Node is another Node
5
    public Node(String data) {
6
        this.data = data;
7
    }
8
}

1
public static void main(String[] args) {
2
    Node n1 = new Node("Have");
3
    Node n2 = new Node("a");
4
    n1.next = n2;
5
    Node n3 = new Node("banana");
6
    n2.next = n3;
7
    Node node = n1;
8
    while (node != null) {
9
        System.out.print(node.data + " ");
10
        node = node.next;
11
    }
12
}

Length of a list#

• How to calculate the length of a list :
  • a) the length of an empty list is 0
  • b) the length of a (non-empty) list is:
    1 + the length of the tail of the list

1
int length (Node ls) {
2
/* pre: ls is a well formed linked list
3
post: length(ls) is the number of nodes in the list starting at ls */
4
    if (ls == null) return 0; // empty list
5
    else return 1 + length(ls.next); // 1+ length of tail of list
6
} /* length */

Practice in class#

• using f(i, j) represents the 𝑗^𝑡ℎ number in the 𝑖^𝑡ℎ line. Pascal’s Triangle(1654)
  Yanghui’s Triangle(1261)

1
public class YanghuiTriangle {
2
    public YanghuiTriangle() {}
3
    public int calculateYanghuiTriangle(int i, int j) {
4
        if (j==1 || i==j) {
5
            return 1;
6
        }
7
        else {
8
            return calculateYanghuiTriangle(i-1, j-1)+calculateYanghuiTriangle(i-1,j);
9
        }
10
    }
11
    public static void main(String[] args) {
12
        YanghuiTriangle yh = new YanghuiTriangle();
13
        System.out.println(yh.calculateYanghuiTriangle(5,3));
14
    }
15
}

• The Tower of Hanoi is a classic mathematical puzzle that consists of three rods (or pillars) and several disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
• The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  3. No disk may be placed on top of a smaller disk.

• Input
  • an integer n, which represents the number of disks on trod A
  • for example:

1
3

• Output
  • displaying the steps of moving the disks;
  • for example:

1
A->C
2
A->B
3
C->B
4
A->C
5
B->A
6
B->C
7
A->C

A->B means moving the top disk from trod A to the top of trod B

In contrast to recursive: iterative#

• The term iterative comes from the Latin iter meaning a journey, as in itinerary, itinerant, iteration, iterator, …
• In programming it refers to making repetitions by using ‘looping’ statements, such as while, for, …

Iterative example - isPresent#

1
static boolean isPresent (int[] a, int x) {
2
    // pre: true
3
    // post: isPresent(a, x) <=> “there is an x in a”
4
    int i = 0;
5
    while(i != a.length && a[i] != x) {
6
        i++;
7
    } // i == a.length || a[i] == x
8
    return i != a.length;
9
}

Recursive example - isPresent()#

1
static boolean isPresentAux(int[] a, int x, int start) {
2
/* pre: true
3
post: isPresent(a, x, start) <=>
4
"there is an x in a", starting from start */
5
    boolean result;
6
    if (start == a.length) result = false; // empty sequence
7
    else if (a[start] == x) result = true; // found x
8
    else result = isPresentAux(a, x, start+1);
9
    return result;
10
}
11
static boolean isPresent (int[] a, int x) {
12
/* pre: true
13
post: isPresent(a, x) <=> “there is an x in a” */
14
    return isPresentAux(a, x, 0);
15
}

Traversing a list: recursive, forward#

• Traversing a (singly) linked list recursively in the forward direction is easy:

1
void traverse (Node ls) {
2
    if (ls != null) {
3
        Process(ls.data); // process head
4
        traverse(ls.next); // traverse tail of list
5
    }
6
} /* traverse */

Traversing a list: recursive, backward#

• Traversing a (singly) linked list recursively in the backward direction is easy too:

1
void reverseTraverse (Node ls) {
2
    if (ls != null) {
3
        reverseTraverse(ls.next);
4
        Process(ls.data);
5
    }
6
} /* reverseTraverse */

How recursion works#

• When a method is called its parameters, local variables and return address are stacked on the method-call stack.
  • Nested calls lead to deeper stacking.
  • A call of a method to itself is just another nested call.

When not to use recursion#

• It is best to use a recursive algorithm when the data structure is itself recursively defined
• Don’t use a recursive approach when a simple iterative approach is available
  • Examples: searching, traversing, and inserting in a list is easy to do iteratively

➢ But, traversing a list backwards (‘backtracking’) is easy to do recursively but hard to do iteratively.

1
int Fib (int n) { /* doubly recursive */
2
/* pre: n >= 0
3
post: Fib(n) is the nth Fibonacci number */
4
    if (n == 0) return 0;
5
    else if (n == 1) return 1;
6
    else return Fib(n - 1) + Fib (n - 2);
7
} /* fib */

1
int Fib (int n) { /* iterative */
2
/* pre: n >= 0
3
post: Fib(n) is the nth Fibonacci number */
4
    int i, x, y, z;
5
    i= 1; x= 1; y= 0;
6
    while (i != n) {
7
        z = x; i = i + 1; x = x + y; y = z;
8
    }
9
    return x;
10
} /* Fib */

Tracing recursion - example#

• Need to take care to know which call is which.

1
int sum(int arr[], int n) {
2
    if (n == 0) return 0;
3
    else {
4
        int smallResult = sum(arr, n - 1);
5
        return smallResult + arr[n - 1];
6
    }
7
}

• Assume the array contains: {2, 4, 6}, and that the call to the sum is:
  • sum(arr, 3); which will sum the first three elements of the array.

When is recursion really useful#

• Really useful if backtracking is involved.
• Call-stack keeps stack of values to return to.

reverseTraverse: iterative version#

• What if we want to traverse the list in reverse order?
  • Needs backtracking.
  • We need to traverse, stacking pointers to nodes, and then return by unstacking them.

1
public static void reverseTraverseIterative(Node first) {
2
    Node p = first;
3
    NodeStack ns = new NodeStack(); // assume such a class available
4
    while (p != null) {
5
        ns.push(p);
6
        p = p.next;
7
    }
8
    while (!ns.empty()) {
9
        System.out.println(ns.pop().data);
10
    }
11
}

Not so simple iteratively.

Questions#

• Which of these operations needs backtracking?
  • Find length of a list
  • Insert in an ordered list
  • Find average value in a list
  • Display above-average values in a list

• What’s the time complexity of the method below that displays all the elements in a LinkedList?

1
static void displayList(LinkedList<String> list) {
2
    for (int i = 0; i < list.size(); i++) {
3
        System.out.println(list.get(i));
4
    }
5
}

Answer:

• get has to traverse through the list to find the ith element, so that is n, but the loop calls get n times,
• so O(n²) - a slow process.

Summary#

• Iteration often more efficient than recursion (but Fibonacci is a very extreme case).
• Sometimes there is a choice of iterative versus recursive.
• Recursive typically closer to definition of data structure.
• Recursion is very useful when backtracking involved.
• Backtracking used in optimal-fitting algorithms - beyond scope of this module.

• After studying the material of this week and attempting the exercises, you should be able to:
  • understand the concept of recursion
  • apply a recursive approach to defining an algorithm
  • know when not to use recursion
  • know how to trace a recursion
• We will use recursion a great deal with trees.

Content#

• The call stack
• Recursion and the call stack
• Exceptions and the call stack
• Finally blocks and the try with resources construct

What information MUST be maintained when a method is called?#

1
public static void main(String[] args) {
2
    double answer = getSum(2,3);
3
// Need to remember which line to return to in the calling method.
4
// This information is no longer needed when the called method returns.
5
    System.out.println(answer);
6
}

1
public static double getSum(double x, double y) {
2
    double sum = x+y;
3
// Need to keep track of the values of local variables and formal parameters.
4
// This information is no longer needed when the called method returns.
5
    return sum;
6
}

1
public static void main(String[] args) {
2
    double answer = getAverage(2,3);
3
    System.out.println(answer);
4
}
5
public static double getAverage(double x, double y){
6
    double average = getSum(x,y)/2;
7
    return average;
8
}
9
public static double getSum(double x, double y) {
10
    double sum = x+y;
11
    return sum;
12
}

1. getAverage is called. Need to keep track of its local variables, etc.
2. getSum is called. Need to keep track of its local variables etc.
3. getSum returns. No longer need information stored in step 2.
4. getAverage returns. No longer need information stored in step 1.

The data most recently added is first to be removed.
What would be a suitable data structure?

The call stack (Schematic)#

1
public static void main(String[] args) {
2
    double answer = getAverage(2,3);
3
    System.out.println(answer);
4
}
5
public static double getAverage(double x, double y){
6
    double average = getSum(x,y)/2;
7
    return average;
8
}
9
public static double getSum(double x, double y) {
10
    double sum = x+y;
11
    return sum;
12
}

Information about each running method is kept in a stack frame, which is pushed onto the stack when the method is called, and popped when it returns.

Visualising the call stack#

A useful tool:
https://cscircles.cemc.uwaterloo.ca/java_visualize/
allows you to visualize the call stack as you run a program

Understanding Recursion#

• There are two ways to convince yourself that a recursive method works:
  1. Reason about it inductively. This is probably the best thing to do first.
  2. Think about what happens to the call stack as it runs. Try this if option 1 is not working for you.

Inductive reasoning#

• Let us use induction to convince ourselves that the method below works. We need to do two things:
  • Convince ourselves that it works for the base case.
  • Convince ourselves that it works for the recursive case, if we assume that any recursive calls do what they are supposed to do.

1
/**Reverse the order of the elements in an ArrayList of Strings**/
2
public static void reverse(ArrayList<String> a) {
3
    if (a.size() > 1) {
4
        String s = a.remove(0);
5
        reverse(a);
6
        a.add(s);
7
    }
8
}

1
/**
2
* Reverse the order of the elements in an ArrayList of Strings
3
*/
4
public static void reverse(ArrayList<String> a) {
5
    if (a.size() > 1) {
6
        String s = a.remove(0);
7
        reverse(a);
8
        a.add(s);
9
    }
10
}

1
/**
2
* Reverse the order of the elements in an ArrayList of Strings
3
*/
4
public static void reverse(ArrayList<String> a) {
5
    if (a.size() > 1) {
6
        String s = a.remove(0);
7
        reverse(a);
8
        a.add(s);
9
    }
10
}

1
/**
2
* Reverse the order of the elements in an ArrayList of Strings
3
*/
4
public static void reverse(ArrayList<String> a) {
5
    if (a.size() > 1) {
6
        String s = a.remove(0);
7
        reverse(a);
8
        a.add(s);
9
    }
10
}

Inductive reasoning#

• We have proved that:
  • Our method works when a.size() == 1 or a.size() == 0.
  • For any n, if the method works for a.size() == n-1, then it also works for a.size() == n.
  • So we can see that…
  • The method works for a.size() == 2 (because of A and B).
  • The method works for a.size() == 3 (because of B and C).
  • The method works for a.size() == 4 (because of B and D)
  • The method works for a.size() == 5 (because of B and E)
  • And so on…
• However if that’s hard to understand, we can also think about what happens on the call stack…

Recursion and the call stack#

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
}

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
}

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
}

Each stack frame has its own separate copy of the variables a and s

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
}

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
}

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
}

Base case. Topmost invocation of the method returns.

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
}

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
}

CHECKED EXCEPTIONS (RECAP)#

1
public static void writeArray(ArrayList<Integer> nums) {
2
    PrintWriter out = new PrintWriter(new FileWriter("OutFile.txt"));
3
    for (int num : nums) {
4
        out.println(num);
5
    }
6
    out.close();
7
}

• This code will not compile because the FileWriter constructor can throw an IOException, which is checked.
• We must either catch this exception, or explicitly declare that the method throws it.

1
public static void writeArray(ArrayList<Integer> nums) {
2
    try {
3
        PrintWriter out = new PrintWriter(new FileWriter("OutFile.txt"));
4
        for (int num : nums) {
5
            out.println(num);
6
        }
7
        out.close();
8
    } catch (IOException ex) {
9
        System.out.println("Error opening file");
10
    }
11
}

1
public static void writeArray(ArrayList<Integer> nums) throws IOException {
2
    PrintWriter out = new PrintWriter(new FileWriter("OutFile.txt"));
3
    for (int num : nums) {
4
        out.println(num);
5
    }
6
    out.close();
7
}

1
public static void writeArray(ArrayList<Integer> nums) {
2
    try {
3
        PrintWriter out = new PrintWriter(new FileWriter("OutFile.txt"));
4
        for (int num : nums) {
5
            out.println(num);
6
        }
7
        out.close();
8
    } catch (IOException ex) {
9
        System.out.println("Error opening file");
10
    }
11
}

Exceptions#

• When an exception is thrown the call stack is “unwound”. That is to say entries are popped from the stack until a suitable catch block is found. The code in the catch block is then executed.
• The catch block might be in the same method as the one that generated the exception, in which case no unwinding is necessary
• If no suitable catch block is found then the program terminates with some sort of error message.

Method E throws an exception that can be handled by Method B’s catch block

Method B has a suitable catch block.

Stack unwinds until we find the catch block

Method B has a suitable catch block.

Stack unwinds until we find the catch block

Method B has a suitable catch block.

Stack unwinds until we find the catch block
Exception is “caught”. Code in catch block is executed.

Method B has a suitable catch block.

• Programming tip:
  • If your code does this, ask yourself if you could have achieved the same effect with an ‘if’ statement.

Finally blocks#

• The code below is intended to read a set of text files and write out the first line of each to an output file.
• However if a problem if an exception is thrown while reading one of the input files, the output file will not be closed. We could fix this using a ‘finally’ block.

1
public static void firstLines(ArrayList<String> fileNames, String outFileName) throws FileNotFoundException {
2
    PrintStream outStream = new PrintStream(outFileName);
3
    for (String file : fileNames) {
4
        FileInputStream inStream = new FileInputStream(file);
5
        Scanner scan = new Scanner(inStream);
6
        String line = scan.nextLine();
7
        outStream.println(line);
8
    }
9
    outStream.close();
10
}

1
public static void firstLines(ArrayList<String> fileNames, String outFileName) throws FileNotFoundException {
2
    PrintStream outStream = new PrintStream(outFileName);
3
    try {
4
        for (String file : fileNames) {
5
            FileInputStream inStream = new FileInputStream(file);
6
            Scanner scan = new Scanner(inStream);
7
            String line = scan.nextLine();
8
            outStream.println(line);
9
        }
10
    } finally {
11
        outStream.close();
12
    }
13
}

• If an exception occurs during the try block, the finally block is executed, then the call stack is unwound until a handler for the exception is found.
• Note that the role of the finally block is not to handle the exception.
• If the try block completes normally then the finally block is still executed.

Try with resources#

• It is common for finally blocks to close resources that have been opened immediately before the try block. If the resource(s) in question implement the interface java.lang.Autocloseable then the try … finally structure can be replaced by a “try with resources” construct, as illustrated below.

1
public static void firstLines(ArrayList<String> fileNames, String outFileName) throws FileNotFoundException {
2
    try (PrintStream outStream = new PrintStream(outFileName)) {
3
        for (String file : fileNames) {
4
            FileInputStream inStream = new FileInputStream(file);
5
            Scanner scan = new Scanner(inStream);
6
            String line = scan.nextLine();
7
            outStream.println(line);
8
        }
9
    }
10
}

Summary#

• When a method is invoked, a stack frame is pushed onto the call stack. When the method returns the frame is popped.
• Each recursive call to a method pushes a separate frame onto the call stack. So you end up with multiple frames, representing multiple invocations of the method.
• When an exception is thrown, the call stack is unwound until a method with a suitable try block is found.
• If a try block is associated with a finally block, the code in this block is always executed. If an exception occurs, the finally block is executed and then the call stack is unwound until a catch block is found.
• A “try with resources” construct can be used as an alternative to a finally block in cases where resources need to be closed.