Recursion

Algorithms
recursion
Catalogue
  1. 1. What is recursion?
    1. 1.1. 1 Look Like
    2. 1.2. 2 In Fact
    3. 1.3. 3 How to Implementate
    4. 1.4. 4 In more details
  2. 2. 1. Recursion与数学计算的结合
    1. 2.1. 50. Pow(x, n) a^b
  3. 3. 2. Recursion与1D or 2D Array的结合
    1. 3.1. 1D Array - Merge Sort, Quick Sort
    2. 3.2. 2D Array
    3. 3.3. LC51 N-Queens
  4. 4. 3. Recursion和LinkedList的结合
  5. 5. 4. Recursion和String的结合
  6. 6. 5. Recursion和Tree的结合
    1. 6.1. Binary tree 往往是最常见的，和recursion结合最紧密的面试题目类型
    2. 6.2. Tree + Recursion 第一类问题:从下往上反值(int ,bool,etc.)
    3. 6.3. 【Way of thinking】 (相当于后序遍历)
    4. 6.4. Follow Up

What is recursion?

Call Stack :

    1. Global accessible resource
    1. Usage : store the local information for each recursion function

1 Look Like

  • function calls itself

2 In Fact

  • Boil down a big problem to smaller ones(size n depends on size n-1, or n-2 or … n/2); Boil down size=n problem to size=n-1，n-2orn/2 problem

3 How to Implementate

  • 1）Base Case:smallest problem to solve
  • 2）Recursive rule:
    how to make the problem smaller (if we can resolve the same problem but with a smaller size, then what is left to do for the current problem size n)

4 In more details

Recursive Function Signature must keep the same logic

1. Recursion与数学计算的结合

50. Pow(x, n) a^b

  • 数学计算常见陷阱:(Corner Case)
    1) 0 as the denominator
    2) 1/3 as an integer? or float? 精度问题
    3) 0^0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public double power(double a, double b) {
    if (a == 0 && b <= 0) {
        return -1;
    } else if (b < 0) {
        return 1 / (double)pow(a,b);
    } else {
        return (double) pow(a, b);
    }
}

public int pow(int a, int b) {
    if (b == 0) { return 1;}

    int halfResult = pow(a, b/2);
    if (b % 2 == 0){
        return halfResult * halfResult;
    } else {
        return halfResult * halfResult * a;
}
1
2
3
4
5
6
7
8
9
10
# Time : O(logn), Space : O(logn)
class Solution(object):
    def myPow(self, x, n):
        if n < 0:
            return self.myPow(1.0/x, -n)
        elif n == 0:
            return 1

        half = self.myPow(x, n//2)
        return half * half * (1 if n%2 == 0 else x)

2. Recursion与1D or 2D Array的结合

1D Array - Merge Sort, Quick Sort

2D Array

LC51 N-Queens

  • 1 逐层(row by row)递归：8 queen -> n queen

    xQxxxxxx
    xxxQxxxx
    xxQxxxxx
    xxxxxxxx
    xxxxxxxx
    xxxxxxxx
    xxxxxxxx
    xxxxxxQx

    • Recursive rule:
      For the i-th queen on the i-th row, we must make sure the Qi does no conflict with all previous queens that have been placed on the board.
      int Position[N] = {1 2 3 5 …}

    • Base Case: The last row is done, 0 row left

    • Recursive rule: iff position(i,j)valid - >go to the next roe:(i+1)
      Time = O($$8^8$$) -> O(8!)

  • 2 How to print 2D array in spiral order (NxN)
    x x x x x
    x x x x x
    x x x x x
    x x x x x

    Recursive rule:
    size = size - 2
    offset = offset + 1

  • 旋转矩阵！

3. Recursion和LinkedList的结合

  • Q1 Reverse a linked list
  • Q2 Reverse linked list pair by pair

4. Recursion和String的结合

  • Q1 Reverse a String using recursion

    abcd -> dcba

  • Q2 A word such as “book” can be abbreviated to 4, “1o1k”, “b3”, “b2k”, etc. Given a string and an abbreviation, return if the string matches the abbreviation. Assume the original string only contains alphabetic characters.

5. Recursion和Tree的结合

Binary tree 往往是最常见的，和recursion结合最紧密的面试题目类型

  • 树本身就是Recursive的结构！
  • 每层的node具备的性质，传递的值和下一层的性质往往一致。比较容易定义recursive rule
  • Base case(generally):null pointer under the leaf node

Tree + Recursion 第一类问题:从下往上反值(int ,bool,etc.)

* 从下往上反值 - getHeight(Node root)
* 从下往上反值 - 统计tree里每个node的左子树有多少个node？
* 从下往上返值 - Find the node with **max difference** in the total number of descendents in its left subtree and right subtree

【Way of thinking】 (相当于后序遍历)

  • 1.What do you expect from your lchild/rhild?
    (usually it is the return type of the recursion type)
  • 2.What do you want to do in the current layer?
  • 3.What do you want to report to your parent?(same as Q1 == Q3)

####LC236 Lowest Common Ancestor of a Binary Tree
从下往上返值，最最经典例题! LCA

  • Method1

use two additional arrays to buffer the prefix from root to a and from root to b

  • Method2 (Recursion)

    Case1: if a is NOT the ancestor of b

    * 1.1 left == null, right == null, return null
* 1.2 left and right reutrn c
* 1.3 either left or right return NOT null, return not NULL

    Case2: if a is the ancestor of b

    * same thing

Follow Up

  • What if either a or b is not int the tree. Can this method take care of this case? A - It depends on your assumption.
  • Assuming that both a and b are in the tree:
    • case1: result = c (c != a && c != b) it means a and b不直接隶属
    • case2a: result = a (a has a descendent which is b)
    • case2b: result = b (b has a descendent which is a)
Share