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?
There is no part of the list to search and the element has not been found
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!)
Last updated