Skip to content

NOTE.md

Latest commit

 

History

History
120 lines (96 loc) · 4.06 KB

NOTE.md

File metadata and controls

120 lines (96 loc) · 4.06 KB

03

Recursion

A recursive function is defined in terms of base cases and recursive steps.

  • In a base case, we compute the result immediately given the inputs to the function call.
  • In a recursive step, we compute the result with the help of one or more recursive calls to this same function, but with the inputs somehow reduced in size or complexity, closer to a base case.

To calculate Factorial of n:

n! = n x (n-1) x ... x 2 x 1

Iterative Implementation

def factorial(n: int) -> int:
    fact = 1
    for i in range(n):
        fact = fact * i
    }
    return fact

Recurrence relation

n! = {
    1           if n = 0
    (n-1)! x n  if n > 0
}

Recursive Implementation

def factorial(n: int) -> int:
    if n = 0:
        return 1
    return n * factorial(n-1)

Divide & Conquer

  • Divide the problem into a number of subproblems that are smaller instances of the same problem.
  • Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
  • Combine the solutions to the subproblems into the solution for the original problem.
def divide_conquer(problem, param1, param2, ...):
    # recursion terminator
    if problem is None:
        process_result
        return

    # prepare data (key is to how to split the problem)
    data = prepare_data(problem)
    subproblems = split_problem(problem, data)

    # conquer subproblems
    subresult1 = self.divide_conquer(subproblems[0], p1, ...)
    subresult2 = self.divide_conquer(subproblems[1], p1, ...)
    subresult3 = self.divide_conquer(subproblems[2], p1, ...)
    ...

    # process and generate the final result
    result = process_result(subresult1, subresult2, subresult3, ...)

    # revert the current level states
  • Sometimes we need to return multiple results (tuple)
  • Sometimes we need global variables to easily update the final result

Leetcode Problems

Backtrack

Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.

result = []
def backtrack(path):
    if end condition:
        result.add(path[:]) # param pass by reference
        return

    if some condition: # Pruning if necessary
        return

    # Get the choice list
    for choice in choices:
        # get rid of the illegal choices
        if exclusive condition:
            continue

        path.append(choice) # Make the choice
        backtrack(path, choices) # enter the next decision tree
        path.pop() # Remove the choice (since it's already made)
  • Time complexity for backtrack algorithm is at least O(N!)
  • Backtrack is a decision tree, updating the result is actually a preorder and/or postorder recursion (DFS)
  • Sometimes we don't need to explicitly maintain the choice list, we derive it using other parameters (e.g. index)
  • Sometimes path can be a string instead of an array, and we use path += 'choice' and path = path[:-1] to make and remove choice

Leetcode Problems