Recursion

1.How to approach?

• Recursive solutions are built of solutions to subproblem

• Three most common approach:

Bottom-Up Approach

• Most intuitive

• We start with how to solve the problem for a simple case then we figure out how to solve the problem for more components and so on. (先解決一個, 再處理下一個)

Top-Down Approach

• Divid the problem for case N into subproblems (將問題分為許多子問題)

Half-and-Half Approach

• We first figure out which half of the array contains the value

• e.g., Binary search

Dynamic Programming & Memoization

• Taking a recursive algorithm and finding the overlapping subproblems

• Cache the result for future recursive calls

• e.g., Fibonacci numbers

Typical solution

• 複雜度: O(N^2) (O(branches ^ depth))

int fibonacci(int i) {
    if (i == 0) {
        return 0;
    }
    if (i == 1) {
        return 1;
    }
    return fibonacci(i - 1) + fibonacci(i - 2)  
}

Top-Down Dynamic Programming (or Memorization)

int fibonacci(int i) {
    return fibonacci(i, new int[n + 1]);  
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) {
        return i;
    }
    
    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }
    return fibonacci(i - 1) + fibonacci(i - 2)  
}

Bottom-Up Programming

int fibonacci(int i) {
    return fibonacci(i, new int[n + 1]);  
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) {
        return i;
    }
    memo[0] = 0;
    memo[1] = 1;
    for (int n = 2; n < i; n++) {
        memo[i] = memo[i - 2] + memo[i - 1];
    }
    return memo[i - 1] + memo[i - 2] 
}

2. What is the best case?

1. There is no part of the list to search and the element has not been found

2. The search element has been found st the mid point of the portion we're searching

3. What is the recursive case?

• Binary search smaller portions of the list where the element might be found

4. Examples

1. Binary search

2.Find all subsets of a set (take Θ (2^n) time )

• 1. What is the best case?

  • When the original set is empty, only the empty set is it's subset

• 2. What is the recursive case?

  • Add the elements to the existing subsets to create new subsets

public static void populateSubsets(List<List<Integar>> subsetList, List<INtegar> numberList) {
    //Recursion base case, the empty superset has just one subset, the empty set
    if (numberList.isEpty()) {
        subsetList.add(new ArrayList<>());
        return;
    }
    //Remove the first number from the original set and find the subsets of the remaining numbers
    int currentNum =  numberList.get(0);
    numberList.remove(0);
    
    populateSubsets(subsetList, numberList);
    List<List<Integar>> iteratingList = ArrayList<>();
    iteratingList.addll(subsetList);
    for (List<Integar> subset : iteratingList) {
        List<Integar> newSubset = ArrayList<>();
        newSubset.addAll(subset);
        newSubset.add(currentNum);
        subsetList.add(newSubset);
    }
}

4.Same binary tree (take Θ (n) time )

binary tree

• A binary tree is one where every node can have a maximum of two children - a left child and right child

• Two binary trees are the same if :

  • Every corresponding node has the same value

  • The structure of the tree at every corresponding node is the same

Algorithm

• 1. What is the best case?

  • 1.A null current node on one tree should correspond to a null in the other tree

  • 2.Node values should be the same at every one

• 2. What is the recursive case?

  • Check that the subtree rooted at every node is the same

Code

• Node class

public static class Node {
    private int id;
    private Node left;
    private Node right;
    
    public Node(int id) {
        thi.id = id;
    }
    
    public int getId() {
        return id;
    }
    
    public Node getLeft() {
        return left;
    }
    
    public Node getRight() {
        return right;
    }
    
    public void addChildren(Node left, Node right) {
        this.left = left;
        this.right = right;
    }
}

• same tree

public static boolean sameTree(Node head1, Node head2) {
    if (head1 == null && head2 == null) {
        returnn true;
    }
    if (head1 == null) {
        returnn false;
    } else if (head1 == null) {
        returnn false;
    }
    
    if (sameTree(head1.getLeft(), head2.getLeft()) &&
        sameTree(head1.getRight(), head2.getRight())) {
        return head1.getId() == head2.getId();  
    }
    return false;
}

5.Implement the paintfill feature from MS paint

• Start with one pixel which has some original color

• Move outwards, if the neighboring pixels have the same original color, color them as well

• Repeat until the borders are reached

• Complexity: O(N)

Base case

• 當目前的pixel沒有相同的顏色時

• 當目前的pixel位置超出螢幕範圍時

Recursive case

• Move outward from the start pixel coloring individual pixels

public static void paintfill(pixel[][] displayScreen, 
         int x, int y, String originalColor, String newColor) {
    //base case
    if (x < 0 || y <0 || 
        x > displayScreen[0].length() || y > displayScreen.length()) {
        return;
    }
    
    if (displayScreen[y][x].getColor() != originalColor) {
        return;
    }
    
    //recursive case
    if (displayScreen[y][x].getColor() == originalColor) {
        displayScreen[y][x].setColor(newColor);
        paintfill(displayScreen, x + 1, y, originalColor, newColor);
        paintfill(displayScreen, x - 1, y, originalColor, newColor);
        paintfill(displayScreen, x, y + 1, originalColor, newColor);
        paintfill(displayScreen, x, y - 1, originalColor, newColor);
    }
}

6.Build a car given all tasks and each task's dependencies

• Say that all the tasks needed to build the car: A, B, C, D, E, F, G, H

  • B depends on A

  • D depends on E

  • C depends on A, B, D

  • F depends on C

• An acceptable order of performing the tasks are:

  • E -> D -> A -> B -> C -> F

  • A -> E -> B -> D -> C -> F

• The tasks and it's dependencies form a directed acyclic graph

• The graph may not be fully connected

Base case

• The current task has been executed, it's marked done.

Recursive case

• Execute dependencies before coming to the current task

Complexity

• O(N)

public static void buildCar(List<Task> taskList) {
    for (Task task : taskList) {
        task.execute();
    }
}

public static class Task {
    private String id;
    private List<Task> dependencyList;
    private boolean done;
    
    public Task(String id, Task...dependencyArray) {
        this.id = id;
        dependencyList = new ArrayList<Task>();
        for (Task task : dependencyArray) {
            dependencyList.add(task);
        }
    } 
    
    public void execute() {
        if (done) {
            return; 
        }
        for (Task task : dependencyArray) {
            task.execute();
        }
        runTask();
    }
    
    private runTask() {
        //perform some operations
        done = true;
    }
}

7.Find all anagrams of a given word

8.Find a path a rat can travel

Base case

• The rat has reached the end cell.

Recursive case

• Keep visiting cells by passing through doors when they exist

• Do not visit cells if they are present in the current path, we don't want the rat to move in circles

public class Cell {
}

public static boolean findPath(Cell current, List<Cell> currentPath) {
    currentPath.add(current);
    if (current.isEnd()) {
        return true;
    }
    
    for (Cell neighbor : current.getNeighbotList()) {
        if (!currentPath.contain(neighbor)) {
            List<Cell> neighborPath = new ArrayList<>();
            neighborPath.addAll(currentPath);
            
            if (findPath(neighbor, neighborPath)) {
                currentPath.clear();
                currentPath.addAll(neighborPath);
                return true;
            }
        }
    }
    return false;
}

9.Place 8 queens on a chessboard so they don't kill each other

Rule

• Remember the queens can move along their rows, columns and along diagonals

• Place one queen at a time, one on each row or one on each column

Tips

• Place a queen in each row or column in a safe position

• See if the remaining queens can be placed safely with the current position of the queen

• Recursively do this till the right positions for all queens have been found

Base case

• The queens have been all placed and we're beyond the boundary of the chessboard

Recursive case

• Keep placing queens in different positions of the same row or column

• Check whether the remaining queens can be successfully placed

Implementation

Place the queens

public static boolean placQueen(int[][] chessboard, int col) {
    if (col >= N) {
        return true;
    }
    
    for (int row = 0; row < N; row++) {
        chessboard[row][col] = 1;
        if (!isSafe(chessboard, row, col)) {
            if (placeQueen(chessboard, col + 1)) {
                return true;
            }
        }
        chessboard[row][col] = 0;
    }
    
    return false;
}

Check if current queen position is safe

public static boolean isSafe(int[][] chessboard, int row, int col) {
    if (!isColumnSafe(chessboard, col)) {
        return false;
    }
    if (!isRowSafe(chessboard, row)) {
        return false;
    }
    if (!isLeftDiagonalSafe(chessboard, row, col)) {
        return false;
    }
    
    return isRightDiagonalSafe(chessboard, row, col);
}

Check the row and the column

public static boolean isColumnSafe(int[][] chessboard, int col) {
    int colSum = 0;
    for (int r = 0; r < N; r++) {
        colSum += chessboard[r][col];
    }
    return colSum == 1;
}

public static boolean isRowSafe(int[][] chessboard, int row) {
    int rowSum = 0;
    for (int c = 0; c < N; c++) {
        rowSum += chessboard[row][c];
    }
    return rowSum == 1;
}

Check the left diagonal

public static boolean isLeftDiagonal(int[][] chessboard, int row, int col) {
    int leftDiagSum = 0;
    int r = 0;
    int c = 0;
    if (row > col) {
        r = row - col;
    } else {
        c = col - row;
    }
    while (r < N && c < N) {
        leftDiagSum += chessboard[r++][c++];
    }
    
    return leftDiagSum == 1;
}

Check the right diagonal

public static boolean isRightDiagonal(int[][] chessboard, int row, int col) {
    int leftDiagSum = 0;
    int r = 0;
    int c = 7;
    if (row + col < N) {
        c = Math.min(col + row, N - 1);
    } else {
        r = (col + row) % (N - 1);
    }
    while (r < N && c >= 0 ) {
        rightDiagSum += chessboard[r++][c--];
    }
    
    return rightDiagSum == 1;
}

Complexity

• O(N!)